第9章 排序

《第9章 排序》由会员分享，可在线阅读，更多相关《第9章 排序（72页珍藏版）》请在金锄头文库上搜索。

1、1,第九章 排序,宋会英,2,概述 插入排序（直接、折半、希尔（重点） 快速排序 （重点） 交换排序（气泡） 选择排序（直接、堆（重点） 归并排序 分配排序（基数）,第九章 排序,3,概述,排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 是待排序数据元素的有限集合。 排序码(key): 通常数据元素有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。,4,排序算法的稳定性: 如果在元素序列中有两 个元素ri和rj, 它们的排序码 ki = kj , 且

2、在排序之前, 元素ri排在rj前面。如果在排序之后, 元素ri仍在元素rj的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。,5,排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。

3、算法执行时所需的附加存储: 评价算法好坏的另一标准。,6,9.2 插入排序 (Insert Sorting),基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上, 直到元素全部插入为止。 基本思想是 : 当插入第i (i1) 个元素时，前面的V0, V1, , Vi-1已经排好序。这时，用Vi的排序码与Vi-1, Vi-2, 的排序码顺序进行比较，找到插入位置即将Vi插入，原来位置上的元素向后顺移。,9.2.1 直接插入排序 (Insert Sort),7,各趟排序结果,i = 1,i = 2,8,0 1 2 3 4 5,i = 4,i = 5,i

4、= 3,9,i = 4 时的排序过程,完成,i = 4 j = 2,i = 4 j = 3,10,25,16,0 1 2 3 4 5 temp,21,49,25*,08,16,25,i = 4 j = 1,i = 4 j = 0,i = 4 j = -1,11,算法分析 设待排序元素个数为currentSize = n, 则该算法的主程序执行n-1趟(第一个元素不用插入)。 排序码比较次数和元素移动次数与元素排序码的初始排列有关。 最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，总的排序码比较次数为 n-1, 元素移动次数为0。,12,最坏情况下

5、, 第 i 趟时第 i 个元素必须与前面 i 个元素都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为：,21,25,49,28,16,08,0 1 2 3 4 5,13,平均情况下排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 基本思想是 : 设在顺序表中有一 个元素序列 V0, V1, , Vn-1。其中, V0, V1, , Vi-1 是已经排好序的元素。在插入Vi 时, 利用折半搜索法寻找Vi 的插入位置。 折半插入排序的算法 #include “dataList.h“,折半插入排序 (Binary Inser

6、tsort),14,template void BinaryInsertSort (dataList /取中点,15,if (temp = low; k-) Lk+1 = Lk; /成块移动,空出插入位置 Llow = temp; /插入 ;,16,算法分析 折半搜索比顺序搜索快, 所以折半插入排序就 平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第 i 个元素时，需要经过 log2i +1 次排序码比较, 才能确定它应插入的位置。因此，将 n 个元素(为推导方便, 设为 n=2k ) 用折半插入排序所进行的排序码比较次数为：

7、折半插入排序是一个稳定的排序方法。,17,当 n 较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。 在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的元素移动次数与直接插入排序相同，依赖于元素的初始排列。,18,希尔排序方法又称为缩小增量排序。该方法的基本思想是 : 设待排序元素序列有 n 个元素, 首先取一个整数 gap n 作为间隔，将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一个子序列中，在每一个子序列中分别施行直接插入排序。,9.2.3 希尔排序 (Shell Sort)

8、（重点）,19,然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap = 1，将所有元素放在同一个序列中排序为止。 开始时 gap 的值较大，子序列中的元素较少，排序速度较快; 随着排序进展，gap 值逐渐变小, 子序列中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然很快。,20,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i = 1,08,49,Gap = 3,25,16,49,25,16,08,49,25*,08,21,25,21,25*,16,21,21,25,49,25*

9、,16,08,0 1 2 3 4 5,21,i = 2,08,49,Gap = 2,25,16,49,16,25*,08,21,25,49,25*,08,16,21,25*,25,22,21,25,49,25*,16,08,0 1 2 3 4 5,21,i = 3,08,Gap = 1,25,16,49,25*,#include “dataList.h“ template ,希尔排序的算法,23,算法分析： 希尔排序是一种不稳定的排序方法。 Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3

10、+1。还有人提出都取奇数为好，也有人提出各 gap 互质为好。 对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。 想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和元素平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。,24,交换排序 ( Exchange Sort ),基本思想是两两比较待排序元素的排序码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之。直到所有

11、元素都排好序为止。 基本方法是：设待排序元素序列中的元素个数为 n。最多作 n-1 趟，i = 1, 2, , n-1。在第 i 趟中从后向前，j = n-1, n-2, , i，顺次两两比较Vj-1.key和Vj.key。如果发生逆序，则交换Vj-1和Vj。,起泡排序 (Bubble Sort),25,21,25,49,25*,16,08,0 1 2 3 4 5,26,25*,0 1 2 3 4 5,i = 4,49,16,Exchang=0,08,25,21,起泡排序,27,基本思想： 任取待排序元素序列中的某个元素作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列： 左

12、侧子序列中所有元素的排序码都小于或等于基准元素的排序码 右侧子序列中所有元素的排序码都大于基准元素的排序码 基准元素则排在这两个子序列中间(这也是该元素最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的元素都排在相应位置上为止。,9.3 快速排序 (Quick Sort)（重点）,28,QuickSort ( List ) if ( List的长度大于1) 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 Rig

13、htList 合并为一个序列List; ,算法描述：,29,21,25,49,25*,16,08,0 1 2 3 4 5,pivot,30,21,25,49,25*,16,08,0 1 2 3 4 5,25*,i = 1 划分,25,16,25,16,08,49,pivotpos,08,25*,49,08,16,25*,25,21,pivotpos,21,比较4次 交换25,16,i,i,pivotpos,21,比较1次 交换49,08,49,low pivotpos,交换21,08,快速排序算法各次快速排序过程,例：初始关键字序列：,(1),(2),60,55,48,37,10,90,84,

14、36,36,55,48,37,10,60,90,10,36,37,55,60,84,(3),10,36,48,60,84,90,最后结果,10,36,37,48,55,60,84,90,37,48,55,84,90,32,快速排序的算法,#include “dataList.h“ void QuickSort (dataList ,33,int dataList:Partition (const int low, const int high) /数据表类的公有函数 int pivotpos = low; Element pivot = Vectorlow; /基准元素 for (int i

15、= low+1; i = high; i+) /检测整个序列, 进行划分 if (Vectori pivot) pivotpos+; if (pivotpos != i) Swap(Vectorpivotpos,Vectori); /小于基准的交换到左侧去,34,Vectorlow = Vectorpivotpos; Vectorpivotpos = pivot; /将基准元素就位 return pivotpos; /返回基准元素位置 ; 算法分析,35,算法quicksort是一个递归的算法, 其递归树如图所示。 算法partition利用序列第一个元素作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是排序码小于基准元素排序码的