《数据结构chap10内部排序》由会员分享，可在线阅读，更多相关《数据结构chap10内部排序（73页珍藏版）》请在金锄头文库上搜索。
1、数据结构 Data Structure,中南大学,中南大学信息院计科系,主讲人：王国军, http:/ 手机：13508486821 办公室：计算机楼406-B,版权申明：本PPT根据数据结构教材所附PPT改编，仅供计科09级/信安09级任课老师和学生使用。,第十章 内部排序,提 纲,10.1 概述10.2 插入排序10.3 快速排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法的比较讨论,排序定义将一组数据元素（或记录）的任意序列，重新排列成一个按关键字有序排列（升序或降序）的序列。,10.1 概述,排序是计算机程序设计中的一种重要运算，是计算机处理数据时一
2、种频繁要做的工作。 关键字将随着用户的要求不同而不同。如：人事档案文件可按年龄、工资或文化水平进行排序，从而获得不同的有序文件。,按待排序记录所在位置 内部排序：待排序记录存放在内存中进行的排序 外部排序：待排序记录的数量很大，以至于内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序,排序分类,插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序,按排序依据原则,简单的排序方法：T(n)=O(n) 先进的排序方法：T(n)=O(nlogn)基数排序：T(n)=O(dn),按排序所需工作量,n为
3、记录的个数，d为关键字的位数,排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置,评价一个排序方法好坏的标准 排序所需比较关键字的次数 排序所需移动记录的次数 排序过程中所需的辅助空间的大小 算法本身的复杂程度,少,少,小,插入排序的准则：在有序序列中插入新的记录以达到扩大有序区的长度的目的。 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。,10.2 插入排序,例1,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3
4、65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,监视哨 L.r0,void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,算法描述,时间复杂度 若待排序记录按关键字从小到大排列(正序)关键字比较次数：,记录移动次数： 0,若待排序记录按关键字从大到小排列
5、(逆序)关键字比较次数：,记录移动次数：,T(n)=O(n),算法评价,若待排序记录是随机的，取上述最大最小的平均值关键字比较次数：,记录移动次数：,空间复杂度：,S(n)=O(1),排序过程：用折半查找方法确定插入位置的排序,例2：,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,.,i=8 20 (6 13 20 30 39 42 70 85 ),折半插入排序,算法描述,void BInsertSort (SqList / 插入 / BInsertSor
6、t,算法评价,T(n)=O(n),时间复杂度：,S(n)=O(1),仅减少了关键字的比较次数,而记录的移动次数不变，所以时间复杂度仍然为,空间复杂度：,希尔排序(缩小增量法),排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d20) for (i=d;i=0 /*递减增量d*/ ,由于没有“负数“的下标，在dk1时需对j循环中以防“出界“另作“j0“的判别，即L.r0 不再起到“监视哨“的作用，而仅仅作为一个暂存记录的空间。,算法描述2,void ShellInsert ( SqList / 插入到正确位置 / if / ShellInsert,void
7、 ShellSort (SqList / 一趟增量为 dltak 的插入排序 / ShellSort,希尔排序特点,子序列的构成不是简单地“逐段分割”，而是将相隔某个增量的记录组成一个子序列。希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n)，所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序。,希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为 2t-k-1 (k= 0, 1, ，t-1)时，希尔排序的时间复杂度为O (n3/2)。,增量序列取法,无除1以外的公因子 采用缩小增量法 最后一个增
8、量值必须为1,基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。,11.3 交换排序,两种交换排序:,(1)冒泡排序(2)快速排序,将第一个记录的关键字与第二个记录的关键字进行比较，若逆序则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。,冒泡排序,排序过程,最简单的一种交换排序方法,例5：,3
9、8,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,27,38,27,38,30,38,49,30,void BubbleSort(SqList / for i / BubbleSort,算法描述,最好情况（正序）比较次数：n-1移动次数：0 最坏情况（逆序）比较次数：,移动次数：,算法评价,T(n)=O(n),时间复杂度：,S(n)=O(1),空间复杂度：,基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序
10、，以达到整个序列有序。 排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs, x=rp.key,快速排序,初始时令i=s, j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。,X=49,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),第二趟排序： ( 13) 27 (38) 49 (76 97 65 50),快速排序结束： 13 27 38 49 50 65 7
11、6 97,49,27,49,65,13,49,49,97,分别进行快速排序：,第三趟排序： ( 13) 27 (38) 49 (50 65) 76 (97),例6：,void QuickSort(RecType R,int s,int t) /*对Rs至Rt的元素进行快速排序*/ int i=s,j=t; RecType temp;if (si /*对右区间递归排序*/ ,划分,算法描述2,void QSort (RcdType R, int s, int t ) / 对记录序列 Rst 进行快速排序 if (s t) / 长度大于1 pivotloc = Partition(R, s, t)
12、; / 对 Rst 进行一趟快排，并返回枢轴位置 QSort(R, s, pivotloc-1); / 对低子序列递归进行排序 QSort(R, pivotloc+1, t); / 对高子序列递归进行排序 / if / QSort,void QuickSort( SqList / QuickSort,int Partition ( RcdType R, int low, int high) / 对记录子序列 Rlowhigh 进行一趟快速排序，并返回枢轴记录 / 所在位置，使得在它之前的记录的关键字均不大于它的关键字， / 而在它之后的记录的关键字均不小于它的关键字 R0 = Rlow; /
13、将枢轴记录移至数组的闲置分量 pivotkey = Rlow.key; / 枢轴记录关键字 while (low=pivotkey) -high; Rlow+ = Rhigh; / 将比枢轴记录小的记录移到低端 while (lowhigh / 返回枢轴位置 / Partition,算法评价,T(n)=O(n),时间复杂度：,最好情况（每次总是选到中间值作枢轴） T(n)=O(nlog2n) 最坏情况（每次总是选到最小或最大元素作枢轴） T(n)=O(n),为避免出现枢轴记录关键字为“最大“或“最小“的情况，通常进行的快速排序采用“三者取中“的改进方案，即以 Rs、Rt 和 R(s+t)/2 三者中关键字介于中值者为枢轴。只要将它和 Rs 互换，一次划分的算法仍不变。,可以证明，快速排序的平均时间复杂度为O (nlogn)，并且在所有平均时间复杂度为O (nlogn)的算法中它是最快的。在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法，如果借用冒泡排序中设置记录“交换与否”的布尔变量的作法，快速排序也适用于已经有序的记录序列。,最坏情况： 一般情况：,S(n)=O(n),空间复杂度：需栈空间以实现递归,S(n)=O(log2n),基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。,
