【精品数据结构】内部排序 (1)

1、数据结构,第十章(下),10.5 归并排序,归并将两个或两个以上的有序表组合成一个新的有序表。,多路归并排序：将三个或三个以上有序子区间合并成一个有序子区间的排序，称为多路归并排序。常见的有三路归并排序、四路归并排序等，具体实现的方法与二路归并排序类似。,算法参见P283, P284,2-路归并排序,排序过程：设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。两两合并，得到n/21个长度为2或1的有序子序列。再两两合并，如此重复，直至得到一个长度为n的有序序列为止。,例：,初始关键字： 49 38 65 97 76 13 27,一趟归并后： 38 49 65 97 13 7

2、6 27,二趟归并后： 38 49 65 97 13 27 76,三趟归并后： 13 27 38 49 65 76 97,例: 对52张扑克牌按以下次序排序： 23A23A 23A23A 两个关键字：花色（ ） 面值（23A） 并且“花色”地位高于“面值”。,10.6 基数排序,10.6.1 多关键字排序,多关键字排序定义：在实际应用中，有时的排序会需要按几种不同排序码来排序。对于多关键字排序（假设有d个关键字），则可以按第1、2、d个关键字的顺序排序，也可以按第d、d-1、d-2、2、1个关键字的顺序排序。,最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每

3、个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。,MSD与LSD不同特点：按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。,多关键字排序方法,10.6.2 链式基数排序,基

4、数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。链式基数排序：用链表作存储结构的基数排序。链式基数排序步骤：设置10个队列，fi和ei分别为第i个队列的头指针和尾指针。第一趟分配对最低位关键字（个位）进行，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同。第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。,例：,算法参见P288,算法评价,分配：T(n)=O(n)收集：T(n)=O(rd)时间复杂度： T(n)=O

5、(d(n+rd) 其中：n记录数 d关键字数 rd关键字取值范围,空间复杂度：S(n)=2rd个队列指针+n个指针域空间故它的空间复杂度为O(rd)。,由于基数排序中值相同的元素的相对位置在分配和收集中，不会发生变化，所以基数排序是一种稳定的排序方法。,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,1,2,2,3,3,4,4,5,6,6,7,7,8,9,10,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0

6、f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,3,4,4,7,7,9,10,3,10,1,6,2,5,8,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,4,4,7,9,2,8,7,9,2,8,3,1,10,6,5,10.7 各种内部排序方法的比较讨论,从时间复杂度比较,从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O

7、(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。,若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。,从空间复杂度比较 归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。,从稳定性比较 直接插入排序、冒泡排序、归并排序是稳定

8、的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。,从算法简单性比较 直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。,各种内排序方法的选择,从时间复杂度选择 对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。,从空间复杂度选择 尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）的2-路归并的排序方法。,一般选择规则 （1）当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。 （2）当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用2-路归并排序为宜。 （3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆