计算机软件技术基础教程课件-12第十二章-排序

第四章排序12.1排序的基本概念所谓排序，就是整理文件中的记录，将它们按照关键字值的递增或递减的顺序排列起来。假定文件中含有n个记录{R1,R2,…,Rn­}，它们的关键字值分别是k1,k2,…,kn，我们将这n个记录重排为Ri1,Ri2,…,Rin，使得ki1≤ki2≤…≤kin（或ki1≥ki2≥…≥kin），这就是排序。12.1排序的基本概念每一种内部排序方法均可在不同的存储结构上实现。通常，文件可有下列三种存储结构：(1)以一维数组作为存储结构，排序过程是对记录本身进行物理重排，即通过比较和判定，把记录移到合适的位置。(2)以链表作为存储结构，排序过程中无须移动记录，仅需修改指针即可，通常把这类排序称为表排序。(3)有的排序方法难以在链表上实现，此时，若仍需要避免排序过程记录的移动，可以为文件建立一个辅助表（如索引表），这样，排序过程中只需对这个辅助的表目进行物理重排，而不移动记录本身。12.2插入排序12.2.1直接插入排序直接插入排序是一种最简单的排序方法。具体做法是在插入第i个记录时，R1,R2,…,Ri-1已排好序，这时将关键字ki依次与关键字ki-1,ki-2,…,k1进行比较，从而找到应该插入的位置，然后将ki插入。12.2插入排序12.2.1直接插入排序图12.1直接插入排序示例12.2插入排序12.2.1直接插入排序整个排序过程只有两种运算，即比较关键字和移动记录。算法中的外循环表示要进行n

1趟插入排序，内循环则表明每一趟排序所需进行的关键字的比较和记录的后移。在文件正序（即关键字递增有序）时，每趟排序的关键字比较次数为1，记录移动次数是2次，即总的比较次数Cmin=n

1，总的移动次数Mmin=2(n

1)；当文件逆序时，关键字的比较次数和记录移动次数均取最大值。对于要插入的第i个记录，均要与前i

1个记录及“监视哨”的关键字进行比较，即每趟要进行i次比较；从移动记录的次数来说，每趟排序中除了上面提到的两次移动外，还需将关键字大于R[i]的记录后移一个位置。12.2插入排序12.2.1直接插入排序因此，总的比较次数和记录的移动次数为：12.2插入排序12.2.2希尔排序希尔排序（Shell’smethod）又称为“缩小增量排序”（DiminishingIncrementSort）。其基本思想是：先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2<d1，重复上述的分组和排序，直至所取的增量dt=1(dt<dt

1<…<d2<d1)为止，此时，所有的记录放在同一组中进行直接插入排序。12.2插入排序12.2.2希尔排序图12.2希尔排序示例12.2插入排序12.2.2希尔排序希尔排序实质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。例如第一趟增量为5，第二趟增量为3，第三趟增量为1。在前两趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，由于此时增量取值较大，所以关键字较小的记录在排序过程中就不是一步一步地向前移动，而是作跳跃式的移动。另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。12.3选择排序选择排序（SelectSort）的基本思想是：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。直接选择排序和堆排序都归属于此类排序。本节主要介绍直接选择排序。12.3选择排序直接选择排序的基本思想是：第一趟排序是在无序区R[0]～R[n

1]中选出最小的记录，将它与R[0]交换；第二趟排序是在无序区R[1]～R[n

1]中选关键字最小的记录，将它与R[1]交换；而第i趟排序时R[0]～R[i

2]已是有序区，在当前的无序区R[i

1]～R[n

1]中选出关键字最小的记录R[k]，将它与无序区中第1个记录R[i

1]交换，使R[1]～R[i

1]变为新的有序区。因为每趟排序都使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，所以，进行n

1趟排序后，整个文件就是递增有序的。其排序过程如图12.3所示。12.3选择排序图12.3直接选择排序示例12.4交换排序12.4.1起泡排序起泡排序（Bubblemethod）也是一种简单的排序方法。它的基本思想是：通过对相邻关键字的比较和交换，使全部记录排列有序。起泡排序的过程是这样的：将关键字按纵向排列，然后自下而上地对每两个相邻的关键字进行比较，若为逆序（即kj

1>kj），则将两个记录交换位置，这样的操作反复进行，直至全部记录都比较、交换完为止。如此一趟排序后，就将关键字最小的记录安排在第一个记录的位置上。然后，对后n

1个记录重复同样操作，再将次小关键字记录安排在第二个记录的位置上。重复上述过程，直至没有记录需要交换为止。至此，整个文件的记录按关键字由小到大的顺序排列完毕。由于在排序过程中，关键字小的记录像气泡一样逐趟向上飘，而大的记录则逐渐下沉，故形象的称为“起泡排序”。起泡排序的过程如图12.4所示。12.4交换排序12.4.1起泡排序图12.4起泡排序示例12.4交换排序12.4.1起泡排序若文件按关键字递增有序，则只需进行一趟排序，比较次数为n

1，记录移动次数为0，即比较次数和记录移动次数均为最小值；若文件按关键字递减有序，则需进行n

1趟排序，比较次数和记录移动次数均为最大值，分别为：12.4交换排序12.4.2快速排序在起泡排序中，比较和交换是在相邻两元素之间进行的，每次交换只能前移或后移一个位置，这样总的比较和移动次数就会增多。快速排序是对起泡排序的一种改进。此时，比较和交换是从两端向中间进行，关键字值较大的元素一次就能交换到后面的位置上，而关键字值较小的元素也能一次就交换到前面位置，即元素移动的距离较大。因此，总的比较和移动的次数就减少了。12.4交换排序12.4.2快速排序快速排序（QuickSort）的基本思想就是通过一趟排序将原有记录分成两部分，然后分别对这两部分进行排序以达到最后所有记录有序。即在当前工作无序区R[1]～R[h]中任取一个记录作为比较的“基准”（不妨记为temp），用此基准将当前无序区划分为左右两个较小的无序子区：R[1]～R[i

1]和R[i+1]～R[h]，且左边的无序子区记录的关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准则位于最终排序的位置上，即：R[1]～R[i

1].key≤temp.key≤R[i+1]～R[h].key(1≤i≤h)当R[1]～R[i

1]和R[i+1]～R[h]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中记录均已排好序为止。12.4交换排序12.4.2快速排序要完成对当前无序区R[1]～R[h]的划分，具体做法是：可设置两个指针i和j，它们的初值分别为i=1和j=h。设基准为无序区中的第一个记录R[i]（即R[1]），并将它保存在变量temp中。令j自h起向左扫描，直到找到第一个关键字小于temp.key的记录R[j]，将R[j]移至i所指的位置上（这相当于交换了R[j]和基准R[i](即temp)的位置，使关键字小于基准关键字的记录移到了基准的左边）；然后，令i自i+1起向右扫描，直至找到第一个关键字大于temp.key的记录R[i]，将R[i]移至j指的位置上（这相当于交换了R[i]和基准R[j](即temp)的位置，使关键字大于基准关键字的记录移到了基准的右边）；接着令j自j

1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准x的最终位置，将x放在此位置上就完成了一次划分。12.4交换排序12.4交换排序图12.5展示了一次划分的过程及整个快速排序的过程。一般来说，快速排序有非常好的时间复杂度，它优于各种排序算法。可以证明，对n个记录进行快速排序的平均时间复杂度为O(nlog2n)。但是，当待排序文件的记录已按关键字有序或基本有序时，情况反而恶化了，原因是在第一趟快速排序中，经过n

1次比较之后，将第一个记录仍定位在它原来的位置上，并得到一个包括n

1个记录的子文件；第二次递归调用，经过n

2次比较，将第二个记录仍定位在它原来的位置上，从而得到一个包括n

2个记录的子文件；依次类推，最后，得到总比较次数为：12.4交换排序这使快速排序蜕变为起泡排序，其时间复杂度为O(n2)。在这种情况下，通常采用“三者取中”的规则加以改进。即在进行一趟快速排序之前，对R[l].key、R[h].key和R[

(l+h)/2

].key进行比较，再将三者中取中值的记录和R[l]交换，就可以改善快速排序在最坏情况下的性能。12.4交换排序在最好情况下，每次划分所取的基准都是无序区的“中值”记录，划分的结果是基准的左、右两个无序子区的长度大致相等。设C(n)表示对长度为n的文件进行快速排序所需的比较次数，显然它应该等于对长度为n的无序区进行划分所需的比较次数n

1，加上递归地对划分所得的左、右两个无序子区（长度≤n/2）进行快速排序所需的比较次数。假设文件长度n=2k，那么总的比较次数为：C(n)≤n+2C(n/2)

≤n+2[n/2+2C(n/22)]=2n+4C(n/22)

≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)

≤……

≤kn+2kC(n/2k)=n(log2n)+nC(1)=O(nlog2n)12.4交换排序因为快速排序的记录移动次数不大于比较的次数，所以，快速排序的最坏时间复杂度应为O(n2)，最好时间复杂度为O(nlog2n)。可以证明：快速排序的平均时间复杂度也是O(nlog2n)，它是目前基于比较的内部排序方法中速度最快的，因而称为快速排序。12.5归并排序归并排序（MergeSort）是一种不同于前面已经介绍过的排序方法。“归并”的含义是将两个或两个以上的有序表合成一个新的有序表。假设初始表含有n个记录，则可看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到

n/2

个长度为2或1的有序子表，再两两归并，如此重复，直至得到一个长度为n的有序子表为止，这种方法称为“二路归并排序”。12.5归并排序图12.6二路归并排序示例12.5归并排序12.5归并排序人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可根据需要应用于不同的场合。选取排序方法时考虑的因素有：①待排序的记录个数n；②记录本身的大小；③关键字的分布情况；④对排序稳定性的要求；⑤语言工具的条件，辅助空间的大小等。依据这些因素，可得出以下几点结论：(1)若待排序的一组记录数目n较小（如n≤50）时，可采用插入排序和选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。12.5归并排序(2)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前内部排序中是最好的方法，当待排序的关键字随机分布时，快速排序的平均运行时间最短；然而堆排序只需一个