《数据结构》-第十章c交换排序

1,第十章 内部排序,10.1 概述,10.2 插入排序,10.2.1 直接插入排序,10.2.2 其他插入排序,10.2.3 希尔排序,10.3 快速排序,10.4 选择排序,10.4.1 简单选择排序,10.4.2 树形选择排序,10.4.3 堆排序,10.5 归并排序,10.6 基数排序,10.6.1 多关键字的排序,10.6.2 链式基数排序,10.7 各种内部排序方法的比较讨论,2,三、交换排序,两种常见的交换排序,起泡排序(Bubble Sort)快速排序(Quick Sort),基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。,3,10.3 快速排序,（1）起泡排序,起泡排序（Bubble Sort）的过程：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（L.r1.key L.r2.key），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。一般地，第i趟起泡排序是从L.r1到L.rn-i1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需要进行k（1kn）趟起泡排序，显然,判别起泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。,4,例如，图10.6展示了起泡排序的一个实例。,图10.6 起泡排序示例,5,起泡排序算法BUBBLESORT(rectype R) int i,j,noswap; rectype temp; for (i=0;i=i;j+) if (Rj+1.keyRj.key) tempRj+1; Rj+1=Rj; Rjtemp; noswapFALSE; if (noswap) break; ,6,起泡排序的效率：,若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1 次关键字间的比较，且不移动记录；,总的时间复杂度为O(n2)。,7,（2）快速排序,快速排序（Quick Sort）是对起泡排序的一种改进。, 主要思想 快速排序的主要思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。, 一趟快速排序,假设待排序序列为L.rs, L.rs+1, , L.rt,首先任意选取一个记录（通常可选为第一个关键字L.rs）作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后落的位置i作分界线，将序列L.rs, , L.rt分割成两个子序列L.rs, L.rs+1, , L.ri1和L.ri1, L.ri+2, , L.rt。这个过程称做一趟快速排序（或一次划分）。,8,一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至lowhigh为止。其算法如算法10.6(a)所示。,9,算法10.6(a)如下： int Partition (SqList / Partition,10,具体实现上述算法时，每交换一对记录需进行3次记录的移动（赋值）的操作。而实际上，在排序过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即lowhigh的位置才是枢轴记录的最后位置。由此可改写上述算法，先将枢轴记录暂存在r0的位置上，排序过程中只作rlow或rhigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。如算法10.6(b)所示。,11,算法10.6(b)如下： int Partition (SqList / Partition,12,(a) 一趟快排过程,13,分别进行快速排序 13 27 38,结束,(b) 排序的全过程,图10.7 快速排序示例, 快速排序算法实现,整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序，如图10.7(b)所示。,14,算法10.7如下： void QSort (SqList /对低高表递归排序 / QSort,15,算法10.8如下： void QuickSort (SqList / QuickSort,16, 快速排序的平均时间,快速排序的平均时间为：,其中，n为待排序序列中记录的个数，k为某个常数。,17,快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。 可以证明，快速排序的平均时间复杂度也是O(nlog2n)。 快速排序是不稳定的排序方法。,18, 快速排序的改进,1“三者取中”法则选取枢轴记录：,即比较L.rs、L.rt.key和 ，取三者中其关键字取中值的记录为枢轴。,2修改“一次划分”,算法：在指针high减1和low增1的同时进行“起泡”操作，即在相邻两个记录处于“逆序”时进行互换，同时在算法中附设两个布尔型变量分别指示指针low和high在