排序算法详解优秀课件.ppt

《排序算法详解优秀课件.ppt》由会员分享，可在线阅读，更多相关《排序算法详解优秀课件.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Hu JunfengHu JunfengHu JunfengHu Junfeng排序算法排序算法详解解第1页，本讲稿共68页问题的提出：问题的提出：为什么要排序？有序表的优点？缺点？构造关系。按照什么原则排序？比较？如何进行排序？第2页，本讲稿共68页基本概念基本概念排序排序（Sorting）：简单地说，排序就是把一组记录一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕1

2、8女第3页，本讲稿共68页作为比较基础的一个(或多个)字段，称为排序码排序码。排序码可以是数值、符号或符号串。排序码排序码不一定是关键码，是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。参与排序的对象，称为记录。一个记录可以包含多个字段。如果记录集合中存在多个排序码排序码相同的记录，经过排序后，排序码排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定稳定的，否则是不稳定不稳定的。排序码 与 关键码（primary key）第4页，本讲稿共68页排序方法可以分为五种插入插入排序、选择选择排序、交换交换排序、分配分配排序和归并归并

3、排序。在排序过程中，全部记录存放在内存，则称为内排序内排序，如果排序过程中需要使用外存，则称为外排序。外排序。本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序的类型第5页，本讲稿共68页排序算法的评价排序算法的评价评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销时间开销是算法好坏的最重要的标志排序的时间开销衡量标准:算法执行中的比较次数（必须）。算法执行中的移动次数（有可能避免）。通常会关注最坏情况和平均情况的开销。第6页，本讲稿共68页插入排序插入排序基本思想：每步将一个待排序的记录，按其排序

4、码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x 顺次选取一个元素顺次选取一个元素插入到合适位置插入到合适位置第7页，本讲稿共68页插入排序的细分类插入排序的细分类n如何插入到已排好序的序列中？v直接插入（从后向前找位置后插入）O(n2)v 二分法插入（按二分法找位置后插入）O(nlog2n)v 表插入排序（按链表查找位置后插入）O(n2)第8页，本讲稿共68页直接插入排序直接插入排序基本思想：假定前面m 个元素已经排序；取第(m+1)个元素，插入到前面的适当位置；一直重复，到m=n 为止。（初始情况下，m=1）第9页，本讲稿共68页 第一趟：第一趟：2323，起始只有一个

5、记录起始只有一个记录 1111,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，80第10页，本讲稿共68页直接插入排序的算法中记录的数据结构直接插入排序的算法中记录的数

6、据结构typedef int KeyType;typedef int DataType;typedef struct KeyType key;/*排序码字段*/DataType info;/*记录的其他字段*/RecordNode;typedef struct int n;/*n为文件中的记录个数，nMAXNUM*/RecordNode*record;SortObject;第11页，本讲稿共68页直接插入排序算法复杂度评价直接插入排序算法复杂度评价极端情况下：极端情况下：最小比较次数最小比较次数每个记录仅比较一次每个记录仅比较一次最大比较次数最大比较次数每个记录比较已每个记录比较已排好序的记录

7、长度排好序的记录长度第12页，本讲稿共68页直接插入排序算法评价直接插入排序算法评价2 2最小移动次数最小移动次数 最大移动次数最大移动次数 第13页，本讲稿共68页直接插入排序算法评价直接插入排序算法评价3初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序，则时间复杂度为O(n2)第14页，本讲稿共68页直接插入排序算法评价直接插入排序算法评价4 平均复杂度平均复杂度插插入入记记录录Ri-1Ri-1，有有i i种种可可能能的的插插入入位位置置，即即插插入入到到第第0 0，1 1，i-1i-1位位置置上上，假假设设每

8、每种种情情况况发发生生的的概概率率是是相相等等的的，均均为为 p pj j=1/i(j=0,1,i-1)=1/i(j=0,1,i-1)比比较较次次数数为为C Cj j=j+1(j=0,i-2,i-2)=j+1(j=0,i-2,i-2)，则则插插入入记记录录R Ri-1i-1的的平平均比较次数为均比较次数为第15页，本讲稿共68页直接插入排序算法评价直接插入排序算法评价5 平均复杂度平均复杂度直接插入排序的 总的比较次数为：第16页，本讲稿共68页直接插入排序算法评价直接插入排序算法评价直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n)=O(n

9、2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)直接插入排序是稳定的第17页，本讲稿共68页存储结构与算法优化存储结构与算法优化顺序存储结构：二分插入算法，减少比较次数。链式存储结构：减少移动次数。第18页，本讲稿共68页二分法插入排序二分法插入排序特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入二分法插入排序限制：必须采用顺序存储顺序存储方式。第19页，本讲稿共68页例：有例：有6个记录，前个记录，前5 个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。15 27 36 53 69 42 lo

10、w 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 )第20页，本讲稿共68页二分法插入排序算法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=right)mid=(left+right)/2；if(temp.key recor

11、dmid.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 /binSort第21页，本讲稿共68页二分插入排序比较次数二分插入排序比较次数二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，如果 ，则无论排序码的大小，都恰好经过 次比较才能确定插入位置，如果，则比较次数为j+1，因此，将n(n=2k)个记录排序的总比较次数为第22页，本讲稿共6

12、8页二分法插入排序方法性能分析二分法插入排序方法性能分析当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为n平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为T(n)=O(n2)二分插入排序法是稳定的排序算法,在检索时采用leftright结束，left、right的修改原则是：temp.key recordmid.key，保证排序是稳定的。第23页，本讲稿共68页结论结论移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)二分法插入排序算法的平均

13、时间复杂度为 T(n)=O(n2)二分法插入排序是稳定的第24页，本讲稿共68页表插入排序表插入排序表插入排序是在直接插入排序的基础上减少移动的次数。基本思想:在记录中设置一个指针字段，记录用链表连接插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。第25页，本讲稿共68页struct Node;/*单链表结点类型*/typedef struct Node ListNode;struct Node KeyType key;/*排序码字段*/DataType info;/*记录的其它字段*/ListNode*next;/*记录的

14、指针字段*/;typedef ListNode*LinkList;表插入算法中记录的数据结构表插入算法中记录的数据结构第26页，本讲稿共68页表插入排序的算法性能分析表插入排序的算法性能分析 第i趟排序：最多比较次数i次，最少比较次数1次。n-1趟总的比较次数：最多：最少：n-1 记录移动次数：0 时间效率：O(n2)辅助空间：O(n)指针 稳定性：p-key key保证稳定的排序。第27页，本讲稿共68页选择排序选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。关键问题：在剩余的待排序记录序列中找到最小关键码记录。方法：直接选择排序堆排序。第2

15、8页，本讲稿共68页直接选择排序直接选择排序方法是首先在所有记录中选出排序码最小的记录，与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推，直到所有记录排好序第29页，本讲稿共68页直接选择排序性能分析直接选择排序性能分析选择排序的比较次数与记录的初始状态无关。第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。总的比较次数：移动次数：Mmin=0 (初始为正序时）最多移动次数：Mmax=3(n-1)(初始为逆序时，每趟1次交换，3次移动完成）时间复杂度：T(n)=O(n2)，辅助空间1个记录单位：Temp，稳定性：不稳定的排序。第30页，本

16、讲稿共68页31起泡排序起泡排序方法先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换然后对新的第二个记录R1与第三个记录R2作同样的处理依次类推，直到处理完第n-1个记录和第n个记录从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡经过这次起泡，n个记录中最大者被安置在第n个位置上第31页，本讲稿共68页32此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序可以设置一个标志noswap表示本次起泡是否有记录交

17、换，如果没有交换则表示整个排序过程完成起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序起泡排序方法起泡排序方法第32页，本讲稿共68页若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值起泡排序的算法评价起泡排序的算法评价第33页，本讲稿共68页起泡排序的算法评价起泡排序的算法评价(续续)起泡排序最好时间复杂度是O(

18、n)起泡排序最坏时间复杂度为O(n2)起泡排序平均时间复杂度为O(n2)起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)起泡排序是稳定的第34页，本讲稿共68页归并排序（归并排序（merge sort）归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是:只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。第35页，本讲稿共68页归并排序（归并排序（merge sort）88149825625279302331Divide and Conquer 第36页，本讲稿共68页Mer

19、ge 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.第37页，本讲稿共68页Merge SortMerge two sorted lists into one 25,31,52,88,9814,23,30,62,7914,23,25,30,31,52,62,79,88,98第38页，本讲稿共68页第39页，本讲稿共68页二

20、路归并算法的基本思路：二路归并算法的基本思路：两组归并算法merge：按low,m,high归并两组记录。结果放于low,high之间。void merge(RecordNode*r,RecordNode*r1,int low,int m,int high)一趟归并算法mergePass：两两归并长度为length的一组记录：void mergePass(RecordNode*r,RecordNode*r1,int n,int length)第40页，本讲稿共68页具有n个记录的文件排序，必须做log2n 趟归并，每趟归并所花费的时间是O(n)二路归并排序算法的时间复杂度为T(n)=O(nlo

21、g2n)算法中增加了一个数组record，算法的辅助空间为S(n)=O(n)二路归并排序是稳定的算法评价算法评价第41页，本讲稿共68页Quicksort第42页，本讲稿共68页Quicksort(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.

22、Combine:Since the subarrays are sorted in place,no work is needed to combine them:the entire array Ap r is now sorted.第43页，本讲稿共68页Quicksort(cont.)O(n)?第44页，本讲稿共68页分配排序分配排序分配排序是一种借助多关键码排序思想对单关键码排序的方法第45页，本讲稿共68页例子扑克牌排序要求:每张扑克牌具有两个属性花色（梅花方块红心黑桃）和面值（2310JQKA），且花色的地位高于面值，排序后为梅花2，梅花A，方块2，方块A，红心2，红心A，黑桃2，

23、黑桃A分配排序例子第46页，本讲稿共68页扑克牌排序方法扑克牌排序方法排序有以下两种方法第一是先将牌按花色分成4堆，然后将每堆按面值从小到大排序，最后按花色从小到大迭在一起第二种是先将牌按面值大小分成13堆，然后从小到大把它们收集起来，再按花色分成4堆，最后顺序地收集起来第47页，本讲稿共68页对多关键码有序对多关键码有序一般情况下，假设文件F有n个记录F=(R0，R1，Rn-1)且每个记录Ri中含有d个关键码(ki0,ki1,kid-1)，则文件对关键码(k0,k1,kd-1)有序是指文件中任意两个记录Ri和Rj(0ijn-1)满足词典次序有序关系(ki0,ki1,kid-1)(kj0,kj

24、1,kjd-1)其中k0称为最高位关键码，kd-1称为最低位关键码第48页，本讲稿共68页高位优先法:先对最高位关键码k0排序，将文件分成若干堆每堆中的记录都具有相同的k0然后分别就每堆对关键码k1排序，分成若干子堆，如此重复，直到对kd-1排序最后将各堆按次序叠在一起成为一个有序文件低位优先法:从最低位关键码kd-1起排序然后再对高一位关键码kd-2排序如此重复，直到对K0排序后便成为一个有序文件多关键码排序算法多关键码排序算法第49页，本讲稿共68页低位优先法比高位优先法简单，高位优先排序必须将文件逐层分割成若干子文件，然后各子文件独立排序低位优先排序不必分成子堆，对每个关键码都是整个文件

25、参加排序，且可通过若干次“分配”和“收集”实现排序基数排序就是用低位优先法对单逻辑关键码排序的一种方法分配排序算法分配排序算法第50页，本讲稿共68页方法:把每个排序码看成是一个d元组Ki=(Ki0,Ki1,Kid-1)其中每个Ki都是集合C0，C1，Cr-1(C0C1Cr-1)中的值即C0KijCr-1(0in-1,0jd-1)其中r称为基数排序时先按Kid-1从小到大将记录分配到r个堆中然后依次收集，再按Kid-2分配到r个堆中如此反复，直到对Ki0分配、收集，得到的便是排好序的序列基数排序基数排序第51页，本讲稿共68页基数排序方法基数排序方法(续续)基数排序时，为了实现记录的分配和收集

26、，可以设r个队列，排序前为空队列，分配时将记录插入到各自的队列中，收集时将队列中的记录排在一起。第52页，本讲稿共68页初始序列为36，5，16，98，95，47，32，36，48，10，请用基数排序法排序。(1)初始状态 36 5 16 98 95 47 32 36 48 10 例题例题第53页，本讲稿共68页54例题例题(续续)(2)第一趟分配后第一趟分配后第54页，本讲稿共68页(3)第一趟收集后 10 32 5 95 36 16 36 47 98 48(4)第二趟分配后例题例题(续续)第55页，本讲稿共68页例题例题(续续)第56页，本讲稿共68页(5)第二趟收集后 5 10 16 3

27、2 36 36 47 48 95 98 例题例题(续续)第57页，本讲稿共68页基数排序算法中，没有排序码的比较和记录的移动，只是对链表的扫描和指针的赋值，所以，时间耗费主要在修改指针上每趟排序中，清队列的时间为O(r)，将n个记录分配到队列的时间为O(n)，收集的时间为O(r)，因此，一趟排序的时间为O(r+n)总共要进行d趟排序，基数排序的时间复杂度是T(n)=O(d*(r+n)当n较大、d较小，特别是记录的信息量较大时，基数排序非常有效基数排序算法评价基数排序算法评价第58页，本讲稿共68页基数排序中，每个记录中增加了一个next字段，还增加了一个queue数组，故辅助空间为S(n)=O

28、(n+r)基数排序是稳定的基数排序算法评价基数排序算法评价(续续)第59页，本讲稿共68页Counting sort（8.2）第60页，本讲稿共68页COUNTING-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 e

29、qual to i.4(for j lengthA downto 1)do BCAj Aj;/CAj store the rank of Aj CAj CAj-1;第61页，本讲稿共68页Example of counting sort第62页，本讲稿共68页333第63页，本讲稿共68页第64页，本讲稿共68页各种排序方法的比较各种排序方法的比较排序算法之间的比较主要考虑以下几个方面算法的时间复杂度算法的辅助空间排序的稳定性算法结构的复杂性参加排序的数据的规模排序码的初始状态各种排序算法的时间复杂度与辅助空间及算法的稳定性如下表所示第65页，本讲稿共68页算法评价算法评价-2当数据规模n较小

30、时，n2和nlog2n的差别不大，则采用简单的排序方法比较合适如直接插入排序或直接选择排序等由于直接插入排序法所需记录的移动较多，当对空间的要求不多时，可以采用表插入排序法减少记录的移动当文件的初态已基本有序时，可选择简单的排序方法如直接插入排序或起泡排序等第66页，本讲稿共68页算法评价算法评价-3当数据规模n较大时，应选用速度快的排序算法快速排序法最快，被认为是目前基于比较的排序方法中最好的方法当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，则快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)第67页，本讲稿共68页作业：作业：POJ Dec-18 两道题。不难。晚上 8：00开始。可以ftp提交。第十五次作业。第68页，本讲稿共68页