下载文档原格式
各种排序的实现与效率分析一、排序原理（1）直接插入排序基本原理：这是最简单的一种排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录增1的有序表。
效率分析：该排序算法简洁，易于实现。
从空间来看，他只需要一个记录的辅助空间，即空间复杂度为O（1）.从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。
当待排序列中记录按关键字非递减有序排列（即正序）时，所需进行关键字间的比较次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列（即逆序）时，总的比较次数达最大值（n+2）(n-1)/2，记录移动也达到最大值（n+4）(n-2)/2.由于待排记录是随机的，可取最大值与最小值的平均值，约为n²/4.则直接插入排序的时间复杂度为O（n²）.由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好（正序时时间复杂度可提高至O（n））。
插入排序算法对于大数组，这种算法非常慢。
但是对于小数组，它比其他算法快。
其他算法因为待的数组元素很少，反而使得效率降低。
插入排序还有一个优点就是排序稳定。
（2）折半插入排序基本原理：折半插入是在直接插入排序的基础上实现的，不同的是折半插入排序在将数据插入一个有序表时，采用效率更高的“折半查找”来确定插入位置。
效率分析：由上可知该排序所需存储空间和直接插入排序相同。
从时间上比较，折半插入排序仅减少了关键字间的比较次数，为O(nlogn)。
而记录的移动次数不变。
因此，折半查找排序的时间复杂度为O(nlogn)+O（n²）= O（n²）。
排序稳定。
（3）希尔排序基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源序列的排序度越好效率越高。
Shell 根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔dk 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长dk，对于每一个步长dk 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。
选题一：迷宫与栈问题【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【任务要求】1)首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i，j，d）的形式输出。
其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
2)编写递归形式的算法，求得迷宫中所有可能的通路。
3)以方阵形式输出迷宫及其通路。
【测试数据】迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。
出口出口选题二：算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。
写一个程序，实现基于二叉树表示的算术表达式的操作。
【任务要求】假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。
实现以下操作：1)ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。
2)WriteExpre(E)—用带括弧的中缀表达式输出表达式E。
3)Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。
4)Value(E)—对算术表达式E求值。
5)CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）【测试数据】1)分别输入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。
2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。
选题三：银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：00am，关门5：00pm）起不断有客户进入银行。
数据结构实验报告八种排序算法实验报告一、实验内容编写关于八种排序算法的C语言程序，要求包含直接插入排序、希尔排序、简单项选择择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序。
二、实验步骤各种内部排序算法的比较：1.八种排序算法的复杂度分析〔时间与空间〕。
2.八种排序算法的C语言编程实现。
3.八种排序算法的比较，包括比较次数、移动次数。
三、稳定性，时间复杂度和空间复杂度分析比较时间复杂度函数的情况：时间复杂度函数O(n)的增长情况所以对n较大的排序记录。
一般的选择都是时间复杂度为O(nlog2n)的排序方法。
时间复杂度来说：(1)平方阶(O(n2))排序各类简单排序:直接插入、直接选择和冒泡排序；(2)线性对数阶(O(nlog2n))排序快速排序、堆排序和归并排序；(3)O(n1+§))排序,§是介于0和1之间的常数。
希尔排序(4)线性阶(O(n))排序基数排序，此外还有桶、箱排序。
说明：当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O〔n〕；而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O〔n2〕；原表是否有序，对简单项选择择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
稳定性：排序算法的稳定性:假设待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；假设经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。
稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。
基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。
另外，如果排序算法稳定，可以防止多余的比较；稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序四、设计细节排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
- - . - 总结资料- 数据结构实训报告
实验名称：数据结构 题目：部排序比较 专业： 班级： ： 学号： 实验日期：
一、实验目的：通过随机数据比较各部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。 二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。
三、实验容 1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种； 2 、待排序的元素的关键字为整数； 3 、比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。 4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。 5、最后要对结果作简单的分析。 6、测试数据：用伪随机数产生程序产生。
四、实验编程结果或过程： 1. 数据定义 - - . - 总结资料- typedef struct { KeyType key; }RedType; typedef struct {
RedType r[MAXSIZE+1]; int length; }SqList;
2. 函数如下，代码详见文件“排序比较.cpp” int Create_Sq(SqList &L) void Bubble_sort(SqList &L)//冒泡排序 void InsertSort(SqList &L)//插入排序 void SelectSort(SqList &L) //简单选择排序 int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法
void QuickSort(SqList &L) void ShellInsert(SqList &L,int dk)//希尔排序
void ShellSort(SqList &L,int dlta[ ])
3. 运行测试结果，运行结果无误，如下图 语速个数为20
元素个数为100 -
- . - 总结资料- 错误调试 无。 影响排序的因素： 1、待排序的记录数目n 的大小。 2、记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。 3、关键字的结构及其分布情况。 4、对排序稳定性的要求 五、实验总结： - - . - 总结资料- （1）实验中的存在问题和提高
1、存在问题：程序有待增强。 2、提高：界面处理简洁。 （2）收获与体会： 1、随机数的生成； 2、排序的算法的比较次数与移动次数的计算 3、各种排序的算法
附录 源程序 /*一.选择排序算法： 算法基本原理： 一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。 算法实现：*/ #include //选择排序，如果第一个数字小于后面的则向后移动，依次类推
//该排序时不稳定的，时间复杂度是N平方 int main() {
int array[10] = {112,4,2,3,5,33,6,7,8,9};//定义一个数组
int length = sizeof(array)/sizeof(array[0]);//得到数组的长度 int min, k=0, s=0, i=0, j=0;//k保存临时结果，s，i，j为循环变量 //选择排序开始 for(i=0;i{min=i; - - . - 总结资料- for(j=i+1;j
{ if(array[i]>array[j]) {min=j; } if(min!=i) {k=array[i]; array[i]=array[j]; array[j]=k; } } }
//选择排序结束，输出显示排序的结果 for(s=0; s{ printf("%d \n",array[s]); } return 0; }
/*二.冒泡排序 算法基本原理： 对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。 算法实现：*/ #include //冒泡排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就
把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方 int main() { - - . - 总结资料- int array[10] = {1,2,11,22,33,4,23,234,4,6};
int length = sizeof(array)/sizeof(array[0]); int k=0, s=0, i=0, j=0, m=0;
//冒泡排序开始 for(i = length-1;i>0;i=k) { for(j=0, k=0;j{
if(array[j]>array[j+1])//把比较出来大的数据向后移动 { m=array[j]; array[j]=array[j+1]; array[j+1]=m; k=j; } } }
//冒泡排序结束，输出显示排序的结果 for(s=0; s{ printf("%d \n",array[s]); } return 0; }
/*三.快速排序
算法基本原理： 快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 算法实现：*/ #include //快速排序开始，使用递归方法，取其中一个数（任意基本上都是以第一个为准），先
从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大， - - . - 总结资料- 则交换之，再到前面比较，如果前面的比这个数小交换之再和后面的比较，第一趟下来
比它小的就在前面了，比它大的就在后面喽，然后再把该数组分成两部分使用递归，直到最后排序完成 void paixu(int array[], int low, int hight) { int i,j,t,m; if(low{ i = low; j = hight; t = array[low]; while(i{
while(it)//开始和后面的比较，如果后面的比他大继续，如果后面的比
它小交换之 { j--; }
if(i{ m=array[i]; array[i]=array[j]; array[j]=m;
i++;//让前面的向后移动一个继续比较 } while(i
果大于交换之 { i++; } if(i{ m=array[j]; array[j]=array[i]; array[i]=m; j--; } - - . - 总结资料- }
array[i]=t;//第一次比较结束，把i放到中间的位置，也即在i前面都比i小，在i后面
都比i大 paixu(array, low, i-1);//前面部分实现递归 paixu(array, i+1, hight);//后面部分实现递归 } } int main() { int s=0; int array[] = {10,22,3,21,45,67,2,11,110,453}; int length = sizeof(array)/sizeof(array[0]); paixu(array,s,length-1); for(s=0;s{ printf("%d \n",array[s]); } return 0; }
/*四.插入排序 概述： 有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为⊙(㎡)。是稳定的排序方法。 插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。
