算法与数据结构：第十章 内部排序

1、第十章. 内部排序 （Chapter 10. Internal Sorting,排序又称分类，是计算机中最重要的操作，它是将一个数据元素（或记录）的任意序列排列成一个按关键字有序的序列,若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj (1i jn)，即排序前 Ri 在 Rj 前，若在排序后 Ri 仍在 Rj 前，则称排序是稳定的,稳定的排序方法（stable sorting method,排序（sorting,不稳定的排序方法（unstable sorting method,待排序列中存在两个或以上关键字相等的记录，设Ki=Kj (1i jn)，即排序前 Ri 在 Rj 前，若在排序

2、后 Rj 却在 Ri前，则称排序是不稳定稳定的,内部排序（internal sorting,待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序,外部排序（external sorting,待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序,1、比较操作：比较两个关键字值的大小的操作,排序过程中的两种基本操作,2、移动操作：将记录从一个位置移动到另一个位置的操作,待排序列的三种存储结构,1、顺序存储：存储在地址连续的一组存储单元中（以此为例,2、链式存储：存储在地址不连续的一组存储单元（链表）中,3、地址存储：记录顺

3、序存储，另设关键字和记录地址排序,typedef struct keytype key; . . . . . . elemtype; typedef struct elemtype * elem; int length; sqlist,10.1 插入排序,一、直接插入排序,直接插入排序（straight insertion sort）是一种最简单的排序方法：将记录一个个插入到已排序好的有序表中，从而得到长度增加的新的有序表,void straightinsertsort ( sqlist,排序性能分析,比较次数： 最好情况 n-1 最坏情况 (n+2)(n-1)/2 平均比较次数： (n+4)

4、(n-1)/4,二、折半插入排序,折半插入排序（binary insertion sort）与直接插入排序不同之处在于查找插入位置时不是用顺序查找，而是用折半查找,可见，直接插入排序的时间复杂度为 O(n 2)。但在待排序列有序的的情况下，直接插入排序的时间复杂度下降为 O(n,移动次数： 最好情况 0 最坏情况 (n+4)(n-1)/2 平均移动次数： (n+4)(n-1)/4,折半插入排序的移动次数与直接插入排序相同，只是比较次数少了，因此其时间复杂度也为 O(n 2,三、2-路插入排序,2-路插入排序目的是为了减少排序过程中移动记录的次数，代价是需要 n 个记录的辅助空间 d ：将 r1

5、 赋值给 d1，将 d 看成循环的，其它记录均与 d1 比较，比其小则在 d1 前插入，反之则在 d1 后插入,2-路插入排序的移动次数大约为 n 2 / 2，因此其时间复杂度仍为 O(n 2,四、表插入排序,表插入排序需附设一个指针域，通过改变指针的值来达到不移动记录而得到排序结果的目的,表插入排序是用改变指针来代替移动记录操作，因此其时间复杂度还为 O(n 2,表插入排序的结果是形成了链表，因此查找时只能用顺序查找，为能使用折半查找，需对记录重新排序，但这不影响其时间复杂度,五、希尔排序,希尔排序（Shells method），又称为“缩小增量排序”（diminishing increme

6、nt sort），是一种比较复杂的插入排序,希尔排序的思想是：用一定的增量间隔将待排序列分成多个组，每组都采用简单插入排序；排序完一遍后，缩小增量间隔，再对新的分组采用简单插入排序；反复此过程，直至增量间隔为 1 ，即整个待排序列为一组时，执行一遍简单插入排序后结束,void Shellinsert ( sqlist,希尔排序的时间复杂度与增量序列有关，分析起来很复杂，有人认为为 O ( n 1.5 )，也有人认为为 O ( n 1.3,在以上插入排序中，除希尔排序为不稳定排序外，其余的都是稳定的排序,void Shellsort ( sqlist,10.2 交换排序,一、起泡排序,起泡排序（

7、 bubble sort ）也是一种最简单的排序方法：将相邻两记录一一比较，将关键字较小的记录交换在前面，反复此过程，直到待排序列有序为止,void bubblesort ( sqlist,起泡排序也是一种稳定的排序，时间复杂度为 O ( n 2 ),二、快速排序,快速排序（quick sort）是对起泡排序的改进：将待排序列第一个元素枢轴元素（pivot）放置到序列中的某个位置，使其前面的所有元素的关键字都小于它，后面的所有元素的关键字都大于它；再分别对枢轴元素前面和后面的两段待排序列采用快速排序方法，直至每一段都只剩下一个元素为止,int quickpass ( sqlist,void q

8、uicksort ( sqlist,快速排序是基于比较和交换的排序方法里最快的一种排序，其时间复杂度为 O( n log n,但快速排序的效率不太稳定，在关键字均匀分布时，效率最高；在关键字有序时，效率将退化为 O ( n 2 ) 。如何解决这个难题呢,其实，我们仔细分析就可看出，效率低是因为枢轴元素的选取有问题：我们希望每次选取的枢轴元素都处于待排序列中间位置，但当待排序列有序时，枢轴元素的取值每次都是最大的或最小的。有鉴于此，我们能否考虑在枢轴元素选取时，与部分元素比较一下，选取它们中处于中间大小的元素与枢轴元素交换，作为新的枢轴元素，通常是将处于待排序列头部、尾部和中间的三个元素比较，从

9、而得到新的枢轴元素，这种方法叫“三者取中法”，它能很有效的防止快速排序效率的退化,在空间复杂度上，除静态数据外，由于递归的原因，栈的最大深度在最好的情况下为 O( log n ) ，在最坏的情况下为 n 。在非递归算法中，每次都先对较短的子序列先进行排序能降低栈的深度,快速排序是不稳定排序,void quicksort ( sqlist,快速排序的非递归算法如下,作 业 29. 试证明：当待排序列已呈现出有序状态时，快速排序的时间复杂度为 O ( n 2 )。 30. 试以单链表为存储结构实现简单插入排序,第 六 次 上 机 作 业 输入若干组长度各异的待排序列，分别用快速排序算法和改进的枢轴

10、元素三者取中算法对待排序列进行排序，当待排子序列长度已小于 20时，改用直接插入排序，利用时间函数验证三者取中算法在效率上的提高。（提示： 待排序列的长度一般应为 10000 以上,10.3 选择排序,一、简单选择排序,简单选择排序（simple selection sort）同样也是一种最简单的排序方法：每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止,void simpleselectionsort ( sqlist,二、树形选择排序,借鉴体育比赛中淘汰赛的做法，将两两比赛过的优胜者推举出去与其它组的优胜者比赛，反复此过程，直到决出冠军为止；若能记住每次比

11、赛的结果，则亚军的产生不必再经过此过程，只需将与冠军赛过的每一个运动员逐级进行比赛，即可得到亚军，这就是树形选择排序的思路,树形选择排序（tree selection sort ），又称为锦标赛排序（ tournament sort ）， 是一种按锦标赛思,由于有不相邻元素交换，所以简单选择排序是不稳定的排序，其时间复杂度为 O( n 2,树形选择排序除第一次外，每次都走了树的一条分支，故其时间复杂度为 O( n log n,想进行的排序：将相邻记录两两分为一组进行比较，将关键字较小的记录送往上一层，参加与其它组关键字较小记录的比较，两两比较后再送往上层关键字较小记录，反复此过程，直到只剩下一

12、个记录即为关键字最小记录；将待排序列中该最小记录处置为无穷大，则与其比较过的所有记录按层次逐级比较，直至找到下一个最小记录为止；反复此过程直至序列有序,三、堆排序,堆的定义,堆排序的思路：将待排序列建成堆（初始堆生成）后，则序列的第一个元素（堆顶元素）就一定是序列中的最大元素；将其与序列的最后一个元素交换，将序列长度减一；再将序列建成堆（堆调整）后，堆顶元素,树形排序需要 2n-1 个辅助空间，1964 年J.Willioms 提出另外一种选择排序堆排序（ heap sort,仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度；反复此过程，直至序列长度为一，所得序列即为排序后结

13、果,堆排序的结果为：12，26，32，58，63，74，85，91,那么，应如何建立初始堆？又如何进行堆调整呢？其实，由此例可以看出，建立初始堆就是多次进行堆调整的过程,void heapadjust ( sqlist,void heapsort ( sqlist,堆排序只需一个辅助空间用于交换，其时间复杂度为 O( nlog n )，堆排序是不稳定排序,10.4 归并排序,归并排序（merging sort）的思想是每次将两个或两个以上的有序表合并成一个较长的有序表， 反复此过程， 直到最终只剩下一个有序表为止；单个记录即是最初的有序表,void merge ( sqlist,void me

14、rgesort ( sqlist,以上给出的是二路归并排序的非递归算法，其实归并排序可以很方便的用递归程序实现。归并排序是一种稳定的排序方法，其时间复杂度为 O ( n log n )，辅助空间为 n,作 业 31. 假设有 n 个值不同的元素存于数组 A( 1:n ) 中，另设一数组 C( 1:n )， 对每个元素 A i ， C i 存放 A 中值小于A i 的元素的个数，则 C i =0的元素即为最小元素； 然后根据 C 的值大小将 A 中的元素重新排列。 这种方法称为计数排序，试编程实现之,10.5 基数排序,基数排序（radix sort）是和前面所介绍的排序方法（基于比较的排序方法

15、）完全不同的一种排序方法，它是一种分配排序,多关键字排序,如 52 张扑克牌按以下规则排成有序,可以看出：牌点是决定大小的主要因数（34 10J QKA2），花色则是决定大小的次要因数（DiamondClub HeartSpade），只有在牌点相同时，它才起作用。 因此我们称牌点为高位关键字，花色为,D3C3H3S3D4C4HASAD2C2H2S2,一般的，设有 n 个记录序列（ R1,R2,Rn ），每个记录 Ri 均含有 d 个关键字（ Ki1,Ki2,Kid ）， 则称此序列对关键字（ K1,K2,Kd ）有序，是指序列中任意两个记录 Ri 和 Rj （ 1 i j n ）都满足有序关系

16、：（ Ki1,Ki2,Kid ） （ Kj1,Kj2,Kjd ），其中 K1 称为最高位关键字， Kd 称为最低位关键字,那么应如何实现序列的多关键字排序呢,低位关键字， 决定元素的大小主要看高位关键字，低位关键字只有在高位关键字相等时才发挥作用,LSD法 将待排序列依次按 Kd,Kd-1, K1 进行排序得到有序序列 ，这种排序方法称为最低位优先法 （Least Significant Digit first,MSD法 将序列先按 K1 进行排序，则序列将分成若干子序列，每个子序列中的记录均具有相同的 K1 值；然后再分别对各子序列按 K2 进行排序，则序列将分成更多的子序列；反复此过程，直

17、到全部子序列分别按 Kd 进行了排序后，再将所有子序列依次联接成一个有序序列，这种排序方法称为最高位优先法 （Most Significant Digit first,MSD 与 LSD 各有什么特点呢,MSD 在排序时间上要比 LSD 快些，且每次对排序方法是否稳定没有要求， 但操作起来相对复杂， 因为序列将被分成若干个子序列；而 LSD 每次均对全部记录进行排序，但除按低位关键字排序对稳定性没有要求外 ， 其后的所有排序方法均需是稳定的,LSD 比较容易用多次分配和收集来实现,链式基数排序,基数排序是将关键字看成 d 个关键字复合而成， 即按其基数 rd 所处位置的权值大小分成高、低位关键

18、字，再应用多次分配、收集方法将待排序列排成有序序列。 该方法又称为桶排序（ bucket sort ）， 待排序列用静态链表存储， 是用 2 rd 个指针来作为 rd 个桶的底和盖指针，每次分配即将 n 个记录按其 Ki 分配到各个桶中，收集时则按各桶顺序从上到下依次收集,待排序列： （ 22，12，91，26，74，53，51，85,22,12,91,26,74,53,51,85,收集： （ 91 ，51 ，22，12，53，74，85，26,收集： （12，22，26，51，53，74，85，91,91,22,12,53,74,85,26,51,10.6 前面介绍的各种内部排序方法的比较,一次分配的时间为 O ( n )，一次收集的时间为 O ( rd )，故基数排序的时间复杂度为 O ( d ( n + rd ),基于比较的排序方法，最好的时间复杂度是 O ( n log n)，下面介绍一种公式分组排序方法，