排序算法及算法分析

1、排序算法及算法分析,2008/05/06,2,问题的提出：,为什么要排序？有序表的优点？缺点？ 构造关系。 按照什么原则排序？ 比较？ 如何进行排序？,3,基本概念,排序（Sorting）： 简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）,4,作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。 排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。 参与排序的对象，称为记录。一个记录可以包含多个字段。 如果记录集

2、合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。,排序码 与 关键码（primary key）,5,排序方法可以分为五种插入排序、选择排序、交换排序、分配排序和归并排序。 在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。 本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。,排序的类型,6,排序算法的评价,评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的时间开销是算法好坏的最重要的标志 排

3、序的时间开销衡量标准: 算法执行中的比较次数（必须）。 算法执行中的移动次数（有可能避免）。 通常会关注最坏情况和平均情况的开销。,7,插入排序,选择排序：直接选择排序,交换排序,归并排序,直接插入排序,二分插入排序,起泡排序,快速排序,表插入排序,Shell 排序,堆排序,排序算法,8,插入排序,基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。,x,顺次选取一个元素,插入到合适位置,9,插入排序的细分类,如何插入到已排好序的序列中？ 直接插入（从后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n)

4、 表插入排序（按链表查找位置后插入） O(n2),10,直接插入排序,基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止。 （初始情况下，m = 1）,11,第一趟： 23， 起始只有一个记录 11, 23 11 第二趟： 11，23， 11，23，55 55 第三趟： 11，23，55， 11，23，55，97 97 第四趟： 11，23，55，97， 11，19，23，55，97 19 第五趟： 11，19，23，55，97， 11，19，23，55，80，97 80,示例：23，11，55，97，19，80,12,直接插入排

5、序的算法中记录的数据结构,typedef int KeyType; typedef int DataType; typedef struct KeyType key; /* 排序码字段 */ DataType info; /* 记录的其他字段 */ RecordNode; typedef struct int n; /* n为文件中的记录个数，nMAXNUM */ RecordNode *record; SortObject;,13,直接插入排序算法复杂度评价,极端情况下： 最小比较次数每个记录仅比较一次 最大比较次数每个记录比较已排好序的记录长度,14,直接插入排序算法评价2,最小移动次数

6、最大移动次数,15,直接插入排序算法评价3,初始数据状态相关： 文件初态不同时，直接插入排序所耗费的时间有很大差异。 若文件初态为正序，则算法的时间复杂度为O(n) 若初态为反序，则时间复杂度为O(n2),16,直接插入排序算法评价4 平均复杂度,插入记录Ri-1，有i种可能的插入位置，即插入到第0，1，i-1位置上，假设每种情况发生的概率是相等的，均为 pj = 1/i (j=0,1,i-1) 比较次数为Cj=j+1(j=0,i-2,i-2)，则插入记录Ri-1的平均比较次数为,17,直接插入排序算法评价5 平均复杂度,直接插入排序的 总的比较次数为：,18,直接插入排序算法评价6 小结,直

7、接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2) 直接插入排序的平均时间复杂度为T(n) = O(n2) 算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1) 直接插入排序是稳定的,19,存储结构与算法优化,顺序存储结构： 二分插入算法，减少比较次数。 链式存储结构： 减少移动次数。,20,二分法插入排序,特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序 限制：必须采用顺序存储方式。,21,(highlow ，查找结束，插入位置为low 或high+1 ),( 4236 ),( 4253 ),22,二

8、分法插入排序算法,void binSort(SortObject * pvector) int i, j, left, mid, right;RecordNode temp;for( i = 1; i n; i+ ) temp = pvector- recordi; left = 0; right = i 1; while (left recordmid.key) right = mid-1;,else left = mid+1; /while for(j=i-1; j=left; j-) pvector-recordj+1 = pvector-recordj; if(left != i) p

9、vector-recordleft = temp; / for / binSort,23,二分插入排序比较次数,二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，如果 ，则无论排序码的大小，都恰好经过 次比较才能确定插入位置，如果， 则比较次数为j+1，因此，将n(n=2k)个记录排序的总比较次数为,24,二分法插入排序方法性能分析,当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数 算法的移动次数与直接插入排序算法的相同 最坏的情况为n2/2 最好的情况为n 平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为T(

10、n)= O(n2) 二分插入排序法是稳定的排序算法,在检索时采用leftright结束，left、right的修改原则是：temp.key recordmid.key，保证排序是稳定的。,25,结论,移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2) 二分法插入排序算法的平均时间复杂度为 T(n)= O(n2) 二分法插入排序是稳定的,26,表插入排序,表插入排序是在直接插入排序的基础上减少移动的次数。 基本思想: 在记录中设置一个指针字段，记录用链表连接 插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链 再采用顺序比较的方法找到Ri应插入的

11、位置，将Ri插入链表。,27,struct Node;/* 单链表结点类型 */ typedef struct Node ListNode; struct Node KeyType key;/* 排序码字段 */ DataType info;/* 记录的其它字段 */ ListNode *next;/* 记录的指针字段 */ ; typedef ListNode * LinkList;,表插入算法中记录的数据结构,28,表插入排序的算法性能分析,第i趟排序：最多比较次数i次，最少比较次数1次。 n-1趟总的比较次数： 最多： 最少： n-1 记录移动次数：0 时间效率： O(n2) 辅助空间：

12、 O(n) 指针 稳定性： p-key key保证稳定的排序。,29,shell排序,Shell排序法又称缩小增量法，由D.L.Shell在1959年提出，是对直接插入排序法的改进 思想: 直接插入排序中，当初始序列为逆序时，时间效率最差。若初始序列基本有序时，则大多数记录不需要插入，时间效率大大提高。 另外，当记录数n较小时，n2值受n的值影响不大。 Shell排序正是从这两个方面考虑对直接插入排序进行改进。,30,基本方法,先取一个整数d1n， 把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序 然后取d2 = d1 /k 重复上述分组和排序工作 直到di=1，即所

13、有记录放在一组中为止 各组内的排序可以采用直接插入法，也可以采用后面讲到的其它排序方法，如直接选择排序。,31,示例： 49, 38, 65, 97, 13, 76, 27, 49,原始序列 49 38 65 97 13 76 27 49 d=4 - - - - d=2 13 38 27 49 49 76 65 97 - - d=1 13 38 27 49 49 76 65 97 - 排序结果： 13 27 38 49 49 65 76 97,32,shell排序算法分析,Shell排序算法的速度比直接插入排序快，其时间复杂度分析比较复杂，Shell排序的平均比较次数和平均移动次数都为n1.3

14、左右 Shell排序算法中增加了一个辅助空间temp，因此算法的辅助空间为S(n)=O(1) Shell排序是不稳定的。,33,di有各种不同的取法：,Shell最早提出 d1= ， di+1= ， D.Knuth教授建议取di+1= 。 一般认为di都取成奇数、di之间互素为好，究竟如何选取di最好?理论上至今仍没有完全解决。,34,选择排序,思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。 关键问题：在剩余的待排序记录序列中找到最小关键码记录。 方法： 直接选择排序 堆排序。,35,直接选择排序,方法是 首先在所有记录中选出排序码最小的记录，与第一

15、个记录交换 然后在其余的记录中再选出排序码最小的记录与第二个记录交换 以此类推，直到所有记录排好序,36,Example,37,38,直接选择排序性能分析,选择排序的比较次数与记录的初始状态无关。 第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。 总的比较次数： 移动次数： Mmin = 0 (初始为正序时） 最多移动次数：Mmax = 3(n-1) (初始为逆序时，每趟1次交换，3次移动完成） 时间复杂度：T(n)=O(n2)， 辅助空间1个记录单位：Temp， 稳定性： 不稳定的排序。,39,39,选择排序,直接选择排序 堆排序,40,堆排序(heap sort)

16、,堆的定义：n个排序码序列K=k0,k1,k2,kn-1当且仅当满足如下条件时，称之为堆。 ki k2i+1 ki k2i+1 ki k2i+2ki k2i+2 (i=0,1,2,.,n/2-1) 从定义可以看出，若将此序列看成完全二叉树，则堆的含义表明，完全二叉树中每个非叶结点的排序码均大于等于（或小于等于）其左右子女结点的排序码。 如果堆中根结点的排序码最小，则称为小根堆。 如果堆中根结点的排序码最大，则称为大根堆,41,堆排序的主要思想,设法把原始序列构造成一个堆，使得n个元素的最大值处于序列的第一个位置； 然后交换序列第一个元素(最大值元素)与最后一个元素； （选到一个最大的元素） 再

17、把序列的前n-1个元素组成的子序列构成一个新堆，得到第二大元素，把序列的第一个元素与第n-1个元素交换。 再把序列的前n-2个元素构成一个新堆，如此操作，最终整个序列成为有序序列。,42,关键问题与建堆方法,关键问题：如何将原始序列构成初始堆，丢掉最大值后如何构造新堆？ 初始完全二叉树中， n/2 ， n/2 +1，n-1为叶子，以其为根的子树必然为堆。因此，初始堆建立时，只需要将所有非叶结点为根的子树调整为堆。 建堆方法：可采用“筛选法”为以Ri为根的完全二叉树建堆。 假定：Ri 的左、右子树都是堆，可以把Ri与其左、右子树根结点R2i+1、R2i+2中最大者交换位置。若交换位置后破坏了子树

18、的堆特性，则再对这棵子树重复交换过程，直到以Ri为根结点的子树成为堆 (shift函数)。,43,示例,初始序列为 21，25，49，25*，16，08,44,44,45,45,46,时间效率评价,建初始堆比较次数C1：O(n) 重新建堆比较次数C2：O(nlog2n) 总比较次数=C1+C2 移动次数小于比较次数 因此， 时间复杂度：O（nlog2n） 空间复杂度：O（1） 适用于n值较大的情况。 算法稳定性：不稳定,47,47,内容提要,排序的基本概念 插入排序 选择排序 交换排序 分配排序 归并排序,48,48,交换排序,交换排序的基本方法 两两比较待排序记录的排序码，交换不满足顺序要求

19、的偶对，直到全部满足为止 交换排序的分类 起泡排序 快速排序,49,49,起泡排序,方法 先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换 然后对新的第二个记录R1与第三个记录R2作同样的处理 依次类推，直到处理完第n-1个记录和第n个记录 从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡 经过这次起泡，n个记录中最大者被安置在第n个位置上,50,50,此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。 然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序 可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成 起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序,起泡排序方法,51,51,初始序列为49, 38, 65,