九章内部排序ppt课件.ppt

《九章内部排序ppt课件.ppt》由会员分享，可在线阅读，更多相关《九章内部排序ppt课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、第九章 内部排序,概 述,排序(sorting)将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist)它是待排序数据对象的有限集合。关键字(key)数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。,排序方法的稳定性假设在对象序列中有两 个对象ri和rj,它们的排序码 ki=kj,且在排序之前,对象ri排在rj前面。如果在排序之后,对象ri仍在对象rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。如：待排序列:49,38,65,97,76,13,27,49(稳定)排序得到的序列：1

2、3,27,38,49,49,65,76,97,内排序与外排序内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。,内排序分类依不同原则分插入排序、交换排序、选择排序、归并排序、和基数排序等。依所须工作量分简单排序-时间复杂度O(n2)先进排序方法-时间复杂度O(nlog2n)基数排序-时间复杂度O(dn),排序过程的基本操作：比较两个关键字的大小将记录从一个位置移动

3、到另一个位置待排序记录序列的存储方式：地址连续的一组存储单元（记录之间的次序关系由存储位置决定，实现排序必须借助移动记录）静态链表（记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针）链表排序地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中的地址，在排序之后再按照地址向量中的值调整记录的存储位置地址排序,插入排序,基本思想：每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。直接插入排序(Insert Sort)当插入第i(i 1)个对象时,前面的V0,V1,Vi-

4、1已经排好序。这时,用Vi的排序码与Vi-1,Vi-2,的排序码顺序进行比较,找到插入位置即将Vi插入,原来位置上的对象向后顺移。,直接插入排序过程,0 1 2 3 4 5 6,i=1,i=2,0 1 2 3 4 5 6,21,08,25,49,25*,16,21,25,08,49,25*,16,21,25,08,49,25*,16,21,25,08,49,25*,16,21,25,08,49,25*,16,i=3,21,25,08,49,25*,16,25*,21,25,08,49,25*,16,排序前排序后,i=4,i=5,21,25,08,49,25*,16,16,16,21,25,08

5、,49,25*,16,21,25,08,49,25*,16,21,25,08,49,25*,16,08,0 1 2 3 4 5 6,直接插入排序的算法void InsertSort(SqList/if,算法分析设待排序对象个数为 n,则该算法的主程序执行n-1趟。排序码比较次数和对象移动次数与对象排序码的初始排列有关。直接插入排序的时间复杂度为 O(n2)。直接插入排序是一种稳定的排序方法。,折半插入排序(Binary Insertsort)既然每个要插入记录之前的纪录已经按关键字有序排列，在查找插入位置时就没有必要逐个关键字比较，可以使用折半查找来实现。由此进行的插入排序称之为折半插入排序。

6、,折半插入排序的算法void BInsertSort(SqList/for/BInsertSort,折半插入排序,0 1 2 3 4 5 6,i=1,i=2,0 1 2 3 4 5 6,5,21,3,3,i=3,5,5,21,5,3,21,4,4,i=4,21,5,3,8,8,i=5,21,5,3,16,16,8,4,4,21,3,8,4,5,16,算法分析折半搜索比顺序搜索查找快,所以折半插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序

7、相同。折半插入排序的时间复杂度为O(n2)。折半插入排序是一个稳定的排序方法。,交换排序,基本思想：两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之,直到所有对象都排好序为止。起泡(冒泡)排序(Bubble Sort)设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录地关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。,21,08,25,49,25,16,21,49,25,25,16,08,21,49,25,25,16,08,初始关键字,第一趟

8、排序,第四趟排序,第二趟排序,第三趟排序,21,49,25,25,16,08,第五趟排序,起泡排序的过程,起泡排序的算法typedef int SortData;void BubbleSort(SortData V,int n)int i=1;int exchange=1;while(i=i;j-)if(Vj-1 Vj)/逆序 Swap(Vj-1,Vj);/交换 exchange=1;/标志置为1,有交换 i+;,算法分析第i趟对待排序对象序列Vi-1,Vi,Vn-1进行排序,结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1),其它对象也都向排序的最终位置移动。最多做n-1趟起泡就

9、能把所有对象排好序。最少只需做1趟起泡排序是一个稳定的排序方法。时间复杂度为O(n2)。,快速排序(Quick Sort)任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的排序码都(或=)基准对象的排序码(基准对象也称为枢轴（或支点）记录。)基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。,快速排序算法描述QSort(List)if(List的长度大于1)一趟排序，将序列划分为两个子序列LeftList,Righ

10、tList;QSort(LeftList);QSort(RightList);将两个子序列合并为一个序列;,一趟快速排序的具体做法：设两个指针low和high，设枢轴记录的关键字为pkey，首先从high所指位置起向前搜索找到第一个关键字小于pkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。一趟的结果：以 枢轴 划分 左右两半。,快速排序的过程,21,08,25,49,25*,16,初始关键字,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,

11、21,21,21,08,25,49,25*,16,21,08,25,49,25*,16,21,pkey,一次交换,二次交换,三次交换,四次交换,完成一趟排序,low,high,low,high,high,low,实际上排序过程中不用每次交换枢轴记录和指针所指记录，当一趟排序算法结束时（即low=high）的位置是枢轴记录的最后位置。故先将枢轴记录保存在r0位置上，排序过程中只作rlow或rhigh记录的移动，待一趟排序结束后再将枢轴记录移至正确位置上。,快速排序的过程,21,08,25,49,25*,16,初始关键字,08,25,49,25*,16,21,08,25,49,25*,16,08,

12、25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,21,pkey,一次交换,二次交换,三次交换,四次交换,完成一趟排序,low,high,low,high,high,low,一趟快速排序（枢轴记录不作交换）的算法：int Partition(SqList/返回基准对象位置（主调用于划分）/Partition,08,25,49,25*,16,21,完成一趟排序,左右子序列分别进行快速排序,08,25,49,25*,16,有序序列,08,25,49,25*,16,21,25,49,快速排序的算法void QSort(SqList/QuickSort,算法QS

13、ort是一个递归的算法,其递归树如图所示。算法Partition利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准对象排序码的对象都移到序列左侧,最后基准对象安放到位,函数返回其位置。,算法分析快速排序的趟数取决于递归树的高度。如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。在 n个元素的序列中,对一个对象定位所需时间为 O(n)。若设 t(n)是对 n 个元素的序列进行排序所需的时间,而且每次对一个对象正确定位后,正好把序列划分为长度相等的两个子序列,此时

14、,总的计算时间为O(n log2n),可以证明,函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致,理想情况为 log2(n+1)。因此，要求存储开销为 O(log2n)。在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列。总的排序码比较次数将达n2/2快速排序是一种不稳定的排序方法。,选择排序,基本思想每一趟(例如第 i 趟,i=0,

15、1,n-2)在后面 n-i 个待排序记录中选出排序码最小的记录,作为有序序列中的第 i 个记录。待到第n-2 趟作完,待排序记录只剩下1个,就不用再选了。,简单选择排序(Select Sort)在一组对象 ViVn-1 中选择具有最小排序码的对象；若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调;在这组对象中剔除这个具有最小排序码的对象。在剩下的对象Vi+1Vn-1中重复执行第、步,直到剩余对象只有一个为止。,简单选择排序的过程,最小者 25*无交换,直接选择排序的算法typedef int SortData;void SelectSort(SortData V,int n)

16、for(int i=0;i n-1;i+)int k=i;/选择具有最小排序码的对象 for(int j=i+1;j n;j+)if(Vj Vk)k=j;/当前具最小排序码的对象 if(k!=i)/对换到第 i 个位置 Swap(Vi,Vk);,直接选择排序的排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象,则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为n(n-1)/2。对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数RMN=0，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN=3(n-1)。直接选择排序是一种不稳定的排序方法。,各种排序方法的比较,作业p334,1.(1)(3)481617,