李瑜波数据结构中的排序算法操作论文

1、四川大学软件工程硕士数据结构论文论文题目: 数据结构中的排序算法操作姓名：_李瑜波_学号：_2012年3月16日数据结构中的排序算法操作经济学院 （李瑜波）摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。最后给出了各个算法时间复杂度、空间复杂度和算法稳定性的分析。关键词：排序 时间复杂度 空间复杂度 稳定性 The Algorithms of sorting in data structure Absract: This paper gives a deep e

2、xploration of sorting in data structure, implem-ents the Straight insertion_sort Quick_sort and Simple selection_sort of it. The algorithm we get could be used in the later programming experience. The last of the paper gives time complexity space complexity and stability of every algorithms.Keywords

3、: sorting time complexity space complexity stability1.引言排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。2. 算法

4、的实现2.1 数据结构描述本文研究的待排序的记录采用顺序存储结构，设记录的关键字均为整数。待排序的记录的数据类型为： #define MAXSIZE 20 / 顺序表最大长度的假定值typedef int KeyType; / 不妨设关键字类型为整型typedef struct KeyType key; / 关键字域 InfoType otherinfo; / 其他域RedType; / 记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作监视哨单元 int length; / 顺序表长度SqList; / 顺序表类型2.2 函数功能的描述 假设待排序的

5、记录的关键字序列为：49,38,65,97,76,13,27,49，排序以后的记录按关键字非递减有序 直接插入排序的基本思想：每次将待排序的一个记录按其关键字大小插入到已经排好序的子序列中，直到所有的记录都插入完为止。直接插入排序的过程如图2.1所示：初始关键字 （49） 38 65 97 76 13 27 49i=2: (38) (38 49) 65 97 76 13 27 49i=3: (38) (38 49 65) 97 76 13 27 49i=4: (38) (38 49 65 97) 76 13 27 49i=5: (76) (38 49 65 76 97) 13 27 49i=6

6、: (13) (13 38 49 65 76 97) 27 49i=7: (27) (13 27 38 49 65 76 97) 49i=8: (49) (13 27 38 49 49 65 76 97) 监视哨L.r0图2.1 快速排序的基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序以达到整个序列有序。整个排序过程采用递归方式，一趟快速排序过程如图2.2(a)图所示： pivotkey初始关键字 49 38 65 97 76 13 27 49 i j j 进行1次移动后 27 38 65 97 76

7、 13 49 i i j 进行2次移动后 27 38 97 76 13 65 49 i j j 进行3次移动后 27 38 13 97 76 65 49 i i j 进行4次移动后 27 38 13 76 97 65 49 i j j 完成一趟排序 27 38 13 49 76 97 65 49图 2.2(a)排序的全过程如图2.2(b)所示：初始状态 49 38 65 97 76 13 27 49一次划分之后 27 38 13 49 76 97 65 49分别进行快速排序13 27 38 结束 结束 49 65 76 97 49 65 结束 结束有序序列 13 27 38 49 49 65

8、76 97图 2.2(b) 简单选择排序的基本思想：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录，并和第i(0<i<n+1)个记录交换。简单选择排序的过程如图2.3所示：4938659776132749第1趟 13 38659776492749第2趟1327659776493849第3趟1327389776496549第4趟1327384976976549第5趟1327384949976576第6趟1327384949659776第7趟1327384949657697图2.32.3 算法实现 直接插入排序算法中，第i趟进行的操作为：

9、在含有i-1个记录的有序子序列r1i-1中插入一个记录ri后，变成含有i个记录的有序子序列r1.i；并且为了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨，在自i-1起往前搜索的过程中，可以同时后移记录。算法1 直接插入排序算法Step1:从第二个记录起逐个进行关键字与前面关键字的比较并判断是否把该记录作为哨兵 for ( i=2; i<=L.length; +i ) if(LT(L.ri.key, L.ri-1.key) L.r0 = L.ri; /若“<”，将L.ri复制为哨兵Step2:在进行关键字比较的同时后移记录 for ( j=i-1; LT( L.r0.k

10、ey, L.rj.key ); -j ) L.rj+1 = L.rj; /记录后移Step3:把记录插入到正确的位置 L.rj+1 = L.r0; /插入到正确位置快速排序算法中，一趟快速排序的具体作法为：附设两个指针low和high，他们的初值分别为low和high，设枢轴的关键字为pivokey，则首先从high所指位置起向前搜索找到第一个关键字小于pivokey的记录和枢轴记录相互交换，然后从low所指位置起向后搜索，找到第一个关键字大于的pivokey记录和枢轴记录相互交换，重复这两步直至low=high为止。算法2.1 一趟快速排序算法Step1:选取一个记录作为枢轴，并把关键字附给

11、pivokey L.r0 = L.rlow; /用子表的第一个记录作枢轴记录pivotkey = L.rlow.key; /枢轴记录的关键字Step2: 从high所指位置起向前搜索找到第一个关键字小于pivokey的记录和枢轴记录相互交换,同时把比枢轴小的记录移到低端 while (low<high && L.rhigh.key>=pivotkey) -high; L.rlow = L.rhigh； /将比枢轴记录小的记录移到低端Step3: 从low所指位置起向前搜索找到第一个关键字大于pivokey的记录和枢轴记录相互交换,同时把比枢轴小的记录移到高端 whi

12、le (low<high && L.rlow.key<=pivotkey) +low; L.rhigh = L.rlow /将比枢轴记录大的记录移到高端Step4: 当low=high时，把枢轴记录移到位，并且返回枢轴位置L.rlow = L.r0 /枢轴记录到位return low /返回枢轴位置算法2.2 递归快速排序算法Step1:通过调用QSort函数把整个顺序表一分为二QSort( L, 1, L.length );Step2:把子表再一分为二，然后分别对低子表和高子表进行划分pivotloc = Partition( L, low, high );/将L

13、.rlow.high一分为二QSort( L, low, pivotloc-1 ); /对低子表递归排序QSort( L, pivotloc+1, high ); /对高子表递归排序 简单选择排序中，第i趟进行的操作为：从第i+1个记录到第n个记录中选一个关键字最小的记录，然后与第i个记录进行交换。算法3 简单选择排序算法Step1:从个i+1记录开始从中选一个关键字最小的记录 for ( i=1; i<L.length; +i ) / i 为选择区间下界 j = i; / j 指向当前的初始记录 for ( k=i+1; k<=L.length; +k ) if ( L.rk.k

14、ey<L.rj.key ) j = k; /让j指向当前最小的记录Step2:将找到的最小的记录与第i个记录交换if ( i != j ) L.ri«L.rj; /与第个i记录交换3. 算法分析 3.1直接插入排序从时间复杂度方面来看：当初始记录的关键字序列按非递减有序时，所需进行的关键字间的比较次数达到最小值n-1，记录不需移动；反之当初始记录的关键字序列按非递增有序时，总的比较次数达到最大值(n+2)(n-1)/2,记录移动的次数也达到最大值(n+4)(n-1)/2。而初始记录是随机的，则取上述最大值和最小值的平均值作为直接插入排序的时所需进行关键字间的比较次数和移动记录的

15、次数，约为n2/4。由此，直接插入排序的时间复杂度为O(n2)。从空间复杂度方面来看：直接插入排序仅需要一个记录的附加空间，所以其空间复杂度为O(1)。从排序的稳定性方面来看：直接插入排序算法是一种稳定的排序算法。 3.2 快速排序 从时间复杂度方面来看：最好的情况是每次划分得到的两个子序列的长度大致相等，在这种情况下排序过程所需要的比较次数为O(n·log2n)，最坏的情况是，每次划分得到的子序列有一个为空，而另一个长度为n-1,此时需要进行n-1趟快速排序，整个过程的比较次数为：n(n-1)/2。由于快速排序过程中记录移动的次数不会超过关键字的比较次数，因此，快速排序最好的时间复

16、杂度为O(n·log2n)，最坏的时间复杂度为O(n2)。 从空间复杂度方面来看：快速排序算法需要递归调用，系统内部需要用一个栈来保存参数。当每次划分均匀时，栈的最大深度为ëlog2 nû +1，若每次划分极不平衡时，栈的最大深度为n。所以最好的情况下空间复杂度为O(log2n)，最坏情况下的空间复杂度为O(n)，就平均而言，空间复杂度为O(log2n)。 从排序的稳定性方面来看：快速排序算法是不稳定的。 3.3简单选择排序从时间复杂度方面来看：在一趟排序中关键字的比较次数为n-1次，在第二趟排序中关键字的比较次数为n-2次，第i趟排序中关键字的比较次数为n-i次，总的比较次数为n(n-1)/2。而在各次排序中，记录的移动次数最好的情况是该记录正好处于合适的位置上，不需要移动，此时移动次数为0次，最坏的情况需要交换记录的位置，此时的移动次数为3次，所以总的移动次数最好为0次，最坏为3(n-1)次，由此可知，简单选择排序的时间复杂度为O(n2)。从空间复杂度方面来看：简单选择排序在交换记录时需要一个记录大小的缓