《各种排序算法分析.ppt》由会员分享，可在线阅读，更多相关《各种排序算法分析.ppt（67页珍藏版）》请在金锄头文库上搜索。
1、Hu JunfengHu JunfengHu JunfengHu Junfeng排序算法及算法分析排序算法及算法分析Hu JunfengHu JunfengHu JunfengHu Junfeng问题问题的提出：的提出：为什么要排序？有序表的优点？缺点？构造关系。按照什么原则排序？比较？如何进行排序？2Hu JunfengHu JunfengHu JunfengHu Junfeng基本概念基本概念排序排序（Sorting）： 简单地说，排序就是把一组记录一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004
2、001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕18女3Hu JunfengHu JunfengHu JunfengHu Junfeng作为比较基础的一个(或多个)字段，称为排序码排序码。排序码可以是数值、符号或符号串。排序码排序码不一定是关键码，是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码排序码相同的记录，经过排序后，排序码排序码相同的记录的前后次序保持不变，则这种排序
3、方法称为是稳定稳定的，否则是不稳定不稳定的。排序码 与 关键码（primary key）4Hu JunfengHu JunfengHu JunfengHu Junfeng排序方法可以分为五种插入插入排序、选择选择排序、交换交换排序、分配分配排序和归并归并排序。在排序过程中，全部记录存放在内存，则称为内排序内排序，如果排序过程中需要使用外存，则称为外排序外排序。 本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序的类型5Hu JunfengHu JunfengHu JunfengHu Junfeng排序算法的评价排序算法的评价评价排序算法好坏的标准执行算法所需的时
4、间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。6Hu JunfengHu JunfengHu JunfengHu Junfeng插入排序插入排序基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x 顺次选取一个元素顺次选取一个元素插入到合适位置插入到合适位置7Hu JunfengHu JunfengHu JunfengHu Junfeng插入排序的细分
5、类插入排序的细分类n如何插入到已排好序的序列中？v直接插入（从后向前找位置后插入） O(n2)v 二分法插入（按二分法找位置后插入） O(nlog2n)v 表插入排序（按链表查找位置后插入） O(n2)8Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序直接插入排序基本思想：假定前面m 个元素已经排序；取第(m+1) 个元素，插入到前面的适当位置；一直重复，到m=n 为止。（初始情况下，m = 1）9Hu JunfengHu JunfengHu JunfengHu Junfeng 第一趟：第一趟： 2323， 起始只有一个记录起始只有一个记录 1111
6、, 23 , 23 11 第二趟：第二趟： 1111，2323， 11 11，2323，5555 55 第三趟：第三趟： 1111，2323，5555， 11 11，2323，5555，9797 97 第四趟：第四趟： 1111，2323，5555，9797， 11 11，1919，2323，5555，97 97 19 第五趟：第五趟： 1111，1919，2323，5555，9797， 11 11，1919，2323，5555，8080，97 97 80示例示例：23，11，55，97，19，8010Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序
7、的算法中记录的数据结构直接插入排序的算法中记录的数据结构typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 排序码字段 */ DataType info; /* 记录的其他字段 */ RecordNode;typedef struct int n; /* n为文件中的记录个数，nMAXNUM */ RecordNode *record;SortObject;11Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法直接插入排序算法复杂度评价复杂度评价极端情况下：
8、极端情况下：l最小比较次数最小比较次数每个记录仅比较一次每个记录仅比较一次l最大比较次数最大比较次数每个记录比较已每个记录比较已排好序的记录长度排好序的记录长度12Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法评价直接插入排序算法评价2 2l最小移动次数最小移动次数 l最大移动次数最大移动次数 13Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法评价直接插入排序算法评价3初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序
9、，则时间复杂度为O(n2)14Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法评价直接插入排序算法评价4 平均复杂度平均复杂度插插入入记记录录Ri-1Ri-1，有有i i种种可可能能的的插插入入位位置置，即即插插入入到到第第0 0，1 1，i-1i-1位位置置上上，假假设设每每种种情情况况发发生生的的概概率率是是相相等的，均为等的，均为 p pj j = 1/i (j=0,1, = 1/i (j=0,1,i-1),i-1)比比较较次次数数为为C Cj j=j+1(j=0,=j+1(j=0,i-2,i-2),i-2,i-2)，则则插插入入记记录录R
10、 Ri-1i-1的平均比较次数为的平均比较次数为15Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法评价直接插入排序算法评价5 平均复杂度平均复杂度直接插入排序的 总的比较次数为：16Hu JunfengHu JunfengHu JunfengHu Junfeng直接插入排序算法评价直接插入排序算法评价直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n) = O(n2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1)直接插入排序是稳定的17Hu JunfengHu Ju
11、nfengHu JunfengHu Junfeng存储结构存储结构与算法优化与算法优化顺序存储结构： 二分插入算法，减少比较次数。链式存储结构： 减少移动次数。18Hu JunfengHu JunfengHu JunfengHu Junfeng二分法插入排序二分法插入排序特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分二分法插入法插入排序限制：必须采用顺序存储顺序存储方式。19Hu JunfengHu JunfengHu JunfengHu Junfeng例：有例：有6个记录，前个记录，前5 个已排序的基础上，对第个已排序的基础上，对第6个记录排序
12、。个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 4253 )20Hu JunfengHu JunfengHu JunfengHu Junfeng二分法插入排序算法void binSort(SortObject * pvector) int i, j, left, mid, right;RecordNode temp;for( i = 1; i n; i+ ) temp = pvector- r
13、ecordi; left = 0; right = i 1; while (left = right) mid = (left+right)/2； if (temp.key 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) pvector-recordleft = temp; / for / binSort21Hu JunfengHu JunfengHu JunfengHu Junfen
14、g二分插入排序比较次数二分插入排序比较次数二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，如果 ，则无论排序码的大小，都恰好经过 次比较才能确定插入位置，如果， 则比较次数为j+1，因此，将n(n=2k)个记录排序的总比较次数为22Hu JunfengHu JunfengHu JunfengHu Junfeng二分法插入排序方法性能分析二分法插入排序方法性能分析当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为n平均移动次数为O(n2)二分法插入排序算法的
15、平均时间复杂度为T(n)= O(n2)二分插入排序法是稳定的排序算法,在检索时采用leftright结束，left、right的修改原则是：temp.key recordmid.key，保证排序是稳定的。23Hu JunfengHu JunfengHu JunfengHu Junfeng结论结论移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为 T(n)= O(n2)二分法插入排序是稳定的24Hu JunfengHu JunfengHu JunfengHu Junfeng表插入排序表插入排序表插入排序是在直接插入排序的
16、基础上减少移动的次数。基本思想:在记录中设置一个指针字段，记录用链表连接插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。25Hu JunfengHu JunfengHu JunfengHu Junfengstruct Node;/* 单链表结点类型 */typedef struct Node ListNode;struct Node KeyType key;/* 排序码字段 */ DataType info; /* 记录的其它字段 */ ListNode *next;/* 记录的指针字段 */;typedef ListNod
17、e * LinkList;表插入算法中记录的数据结构表插入算法中记录的数据结构26Hu JunfengHu JunfengHu JunfengHu Junfeng表插入排序的算法性能分析表插入排序的算法性能分析 第i趟排序：最多比较次数i次，最少比较次数1次。 n-1趟总的比较次数： 最多： 最少： n-1 记录移动次数：0 时间效率： O(n2) 辅助空间： O(n) 指针 稳定性： p-key key保证稳定的排序。27Hu JunfengHu JunfengHu JunfengHu Junfeng选择排序选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，
18、直到全部排完。关键问题：在剩余的待排序记录序列中找到最小关键码记录。方法：直接选择排序堆排序。28Hu JunfengHu JunfengHu JunfengHu Junfeng直接选择排序直接选择排序方法是首先在所有记录中选出排序码最小的记录，与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推，直到所有记录排好序29Hu JunfengHu JunfengHu JunfengHu Junfeng直接选择排序性能分析直接选择排序性能分析选择排序的比较次数与记录的初始状态无关。第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。总的比较次数：移
19、动次数： Mmin = 0 (初始为正序时）最多移动次数：Mmax = 3(n-1) (初始为逆序时，每趟1次交换，3次移动完成） 时间复杂度：T(n)=O(n2)，辅助空间1个记录单位：Temp，稳定性： 不稳定的排序。 30Hu JunfengHu JunfengHu JunfengHu Junfeng31起泡排序起泡排序方法先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换然后对新的第二个记录R1与第三个记录R2作同样的处理依次类推，直到处理完第n-1个记录和第n个记录从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡
20、经过这次起泡，n个记录中最大者被安置在第n个位置上31Hu JunfengHu JunfengHu JunfengHu Junfeng32此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序起泡排序方法起泡排序方法32Hu Junfe
21、ngHu JunfengHu JunfengHu Junfeng若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值起泡排序的算法评价起泡排序的算法评价33Hu JunfengHu JunfengHu JunfengHu Junfeng起泡排序的算法评价起泡排序的算法评价(续续)起泡排序最好时间复杂度是O(n)起泡排序最坏时间复杂度为O(n2)起泡排序平均时间复杂度为O(n2)起泡排序算法中增加一个辅助空间temp，辅助空间为S
22、(n)=O(1)起泡排序是稳定的34Hu JunfengHu JunfengHu JunfengHu Junfeng归并排序（归并排序（merge sort）归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是:只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。35Hu JunfengHu JunfengHu JunfengHu Junfeng归并排序（归并排序（merge sort）88149825625279302331Divide and Conquer 36Hu JunfengHu Ju
23、nfengHu JunfengHu JunfengMerge Sort88149825625279302331Split Set into Two (no real work)25,31,52,88,98Get one friend to sort the first half. 14,23,30,62,79Get one friend to sort the second half. 37Hu JunfengHu JunfengHu JunfengHu JunfengMerge SortMerge two sorted lists into one 25,31,52,88,9814,23,3
24、0,62,7914,23,25,30,31,52,62,79,88,9838Hu JunfengHu JunfengHu JunfengHu Junfeng39Hu JunfengHu JunfengHu JunfengHu Junfeng二路归并算法的基本思路：二路归并算法的基本思路：两组归并算法merge： 按low,m,high归并两组记录。结果放于low,high之间。 void merge(RecordNode* r, RecordNode *r1, int low, int m, int high)一趟归并算法mergePass： 两两归并长度为length的一组记录： void
25、mergePass(RecordNode *r, RecordNode *r1, int n, int length) 40Hu JunfengHu JunfengHu JunfengHu Junfeng具有n个记录的文件排序，必须做log2n 趟归并，每趟归并所花费的时间是O(n)二路归并排序算法的时间复杂度为T(n)=O(nlog2n)算法中增加了一个数组record，算法的辅助空间为S(n)=O(n)二路归并排序是稳定的算法评价算法评价41Hu JunfengHu JunfengHu JunfengHu JunfengQuicksort42Hu JunfengHu JunfengHu J
26、unfengHu JunfengQuicksort (cont.)Divide: Partition (rearrange) the array Ap r into two subarrays Ap q - 1 and Aq + 1 r such that： each element of Ap q - 1 AqConquer: Sort the two subarrays Ap q -1 and Aq +1 r by recursive calls to quicksort.Combine: Since the subarrays are sorted in place, no work i
27、s needed to combine them: the entire array Ap r is now sorted.43Hu JunfengHu JunfengHu JunfengHu JunfengQuicksort (cont.)O(n)?44Hu JunfengHu JunfengHu JunfengHu Junfeng分配排序分配排序分配排序是一种借助多关键码排序思想对单关键码排序的方法45Hu JunfengHu JunfengHu JunfengHu Junfeng例子扑克牌排序要求:每张扑克牌具有两个属性花色（梅花方块红心黑桃）和面值（2310JQKA），且花色的地位高于
28、面值，排序后为梅花2，梅花A，方块2，方块A，红心2，红心A，黑桃2，黑桃A分配排序例子46Hu JunfengHu JunfengHu JunfengHu Junfeng扑克牌排序方法扑克牌排序方法排序有以下两种方法第一是先将牌按花色分成4堆，然后将每堆按面值从小到大排序，最后按花色从小到大迭在一起第二种是先将牌按面值大小分成13堆，然后从小到大把它们收集起来，再按花色分成4堆，最后顺序地收集起来47Hu JunfengHu JunfengHu JunfengHu Junfeng对多关键码有序对多关键码有序一般情况下，假设文件F有n个记录F=(R0，R1，Rn-1)且每个记录Ri中含有d个关
29、键码(ki0, ki1, kid-1)，则文件对关键码(k0,k1,kd-1)有序是指文件中任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系(ki0, ki1, kid-1) (kj0, kj1, kjd-1)其中k0称为最高位关键码，kd-1称为最低位关键码48Hu JunfengHu JunfengHu JunfengHu Junfeng高位优先法:先对最高位关键码k0排序，将文件分成若干堆每堆中的记录都具有相同的k0然后分别就每堆对关键码k1排序，分成若干子堆，如此重复，直到对kd-1排序最后将各堆按次序叠在一起成为一个有序文件低位优先法:从最低位关键码kd-1起排序然后再对高
30、一位关键码kd-2排序如此重复，直到对K0排序后便成为一个有序文件多关键码排序算法多关键码排序算法49Hu JunfengHu JunfengHu JunfengHu Junfeng低位优先法比高位优先法简单，高位优先排序必须将文件逐层分割成若干子文件，然后各子文件独立排序低位优先排序不必分成子堆，对每个关键码都是整个文件参加排序，且可通过若干次“分配”和“收集”实现排序基数排序就是用低位优先法对单逻辑关键码排序的一种方法分配排序算法分配排序算法50Hu JunfengHu JunfengHu JunfengHu Junfeng方法:把每个排序码看成是一个d元组Ki=(Ki0, Ki1, Ki
31、d-1)其中每个Ki都是集合C0，C1，Cr-1(C0C1Cr-1)中的值即C0KijCr-1(0in-1,0jd-1)其中r称为基数排序时先按Kid-1从小到大将记录分配到r个堆中然后依次收集，再按Kid-2分配到r个堆中如此反复，直到对Ki0分配、收集，得到的便是排好序的序列基数排序基数排序51Hu JunfengHu JunfengHu JunfengHu Junfeng基数排序方法基数排序方法(续续)基数排序时，为了实现记录的分配和收集，可以设r个队列，排序前为空队列，分配时将记录插入到各自的队列中，收集时将队列中的记录排在一起。52Hu JunfengHu JunfengHu Jun
32、fengHu Junfeng初始序列为36，5，16，98，95，47，32，36，48，10，请用基数排序法排序。(1)初始状态 36 5 16 98 95 47 32 36 48 10 例题例题53Hu JunfengHu JunfengHu JunfengHu Junfeng54例题例题(续续)(2)第一趟分配后第一趟分配后54Hu JunfengHu JunfengHu JunfengHu Junfeng(3)第一趟收集后 10 32 5 95 36 16 36 47 98 48 (4)第二趟分配后例题例题(续续)55Hu JunfengHu JunfengHu JunfengHu J
33、unfeng例题例题(续续)56Hu JunfengHu JunfengHu JunfengHu Junfeng (5)第二趟收集后 5 10 16 32 36 36 47 48 95 98 例题例题(续续)57Hu JunfengHu JunfengHu JunfengHu Junfeng基数排序算法中，没有排序码的比较和记录的移动，只是对链表的扫描和指针的赋值，所以，时间耗费主要在修改指针上每趟排序中，清队列的时间为O(r)，将n个记录分配到队列的时间为O(n)，收集的时间为O(r)，因此，一趟排序的时间为O(r+n)总 共 要 进 行 d趟 排 序 ， 基 数 排 序 的 时 间 复 杂
34、 度 是T(n)=O(d*(r+n)当n较大、d较小，特别是记录的信息量较大时，基数排序非常有效基数排序算法基数排序算法评价评价58Hu JunfengHu JunfengHu JunfengHu Junfeng基数排序中，每个记录中增加了一个next字段，还增加了一个queue数组，故辅助空间为S(n)=O(n+r)基数排序是稳定的基数排序算法评价基数排序算法评价(续续)59Hu JunfengHu JunfengHu JunfengHu JunfengCounting sort （8.2） 60Hu JunfengHu JunfengHu JunfengHu JunfengCOUNTING
35、-SORT(A, B, k)1 (for i 0 to k) do Ci 0 /initialize Ci2 (for j 1 to lengthA ) do CAj CAj + 1 /Ci now contains the number of elements equal to i. 3 (for i 1 to k) do Ci Ci + Ci - 1 /Ci now contains the number of elements less than or equal to i. 4 (for j lengthA downto 1) do BCAj Aj ; /CAj store the r
36、ank of Aj CAj CAj - 1 ; 61Hu JunfengHu JunfengHu JunfengHu JunfengExample of counting sort62Hu JunfengHu JunfengHu JunfengHu Junfeng33363Hu JunfengHu JunfengHu JunfengHu Junfeng64Hu JunfengHu JunfengHu JunfengHu Junfeng各种排序方法的比较各种排序方法的比较排序算法之间的比较主要考虑以下几个方面l算法的时间复杂度l算法的辅助空间l排序的稳定性l算法结构的复杂性l参加排序的数据的规模
37、l排序码的初始状态各种排序算法的时间复杂度与辅助空间及算法的稳定性如下表所示65Hu JunfengHu JunfengHu JunfengHu Junfeng算法评价算法评价-2当数据规模n较小时，n2和nlog2n的差别不大，则采用简单的排序方法比较合适如直接插入排序或直接选择排序等由于直接插入排序法所需记录的移动较多，当对空间的要求不多时，可以采用表插入排序法减少记录的移动当文件的初态已基本有序时，可选择简单的排序方法如直接插入排序或起泡排序等66Hu JunfengHu JunfengHu JunfengHu Junfeng算法评价算法评价-3当数据规模n较大时，应选用速度快的排序算法快速排序法最快，被认为是目前基于比较的排序方法中最好的方法当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，则快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)67
