《数据结构》第七章排序

1、本节内容排序的基本知识王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM排序的意义排序就是将原本无序的序列重新排列成有序的序列。单独的一个数据多个数据的组合(记录)按记录的主关键字(比如学生信息的学号)来排序按记录的次关键字(比如学生信息的姓名、专业等)来排序王道考研/CSKAOYAN.COM排序的稳定性如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。稳定性和排序的性能是没有关系的！12 52 19 45 23 45 92 24

2、12 19 23 24 45 45 52 92排序之后稳定的12 52 19 45 23 45 92 24排序之后12 19 23 24 45 45 52 92不稳定的王道考研/CSKAOYAN.COM直接插入排序直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。5 2 4 6 4 1 3void InsertSort(ElemType A,int n)int i,j;for(i=2;i=n;i+)if(Ai.keyAi-1.key)A0=Ai;/复制为哨兵，A0不存放元素for(j=i-1;A0.keyAj.key;-j)A

3、j+1=Aj;/所有比待插入元素值大的都往后移一位，腾出空位Aj+1=A0; /复制到插入位置 有序序列中只要比这个待插入元素大，循环就继续。每次从后往前查找待插入位置，所以第一个比较的元素就是有序序列的最后一个从第2个元素开始，因为第1个元素可以认为是有序的如果待插入元素比有序序列的最后一个元素还大，那就不用插入了，直接放在原来的位置王道考研/CSKAOYAN.COM直接插入排序分析空间复杂度：在下标为0处存储哨兵，是常数个辅助空间大小，所以空间复杂度为O(1)时间复杂度：最坏情况下：整个序列都是逆序5 4 3 2 14要插到5前面，3要插到4前面，2要插入到3前面. 移动1次 移动2次 移

4、动3次 void InsertSort(ElemType A,int n)int i,j;for(i=2;i=n;i+)if(Ai.keyAi-1.key)A0=Ai;for(j=i-1;A0.keyAj.key;-j)Aj+1=Aj;Aj+1=A0; 即外层for循环每一轮，内层for循环将执行完整。总的移动次数为1+2+3+(n-1)=n(n-1)/2所以最坏情况下时间复杂度为O(n2)王道考研/CSKAOYAN.COM直接插入排序分析时间复杂度：最好情况下：整个序列都是顺序1 2 3 4 5if语句块条件永远不成立void InsertSort(ElemType A,int n)int

5、i,j;for(i=2;i=n;i+)if(Ai.keyAi-1.key)A0=Ai;for(j=i-1;A0.keyAj.key;-j)Aj+1=Aj;Aj+1=A0; 即外层for循环每一轮，都只进行if判断。n个关键字的操作只有n次比较。所以时间复杂度为O(n)王道考研/CSKAOYAN.COM直接插入排序分析稳定性：5 2 4 6 4 1 3当给关键字4排序时，前面的序列已经是2 4 5 6，根据算法比较4和有序序列的关键字大小。当比较4和4的时候，已经不满足A0.keyAj.key。所以直接将4放在4后面。所以直接插入排序是稳定性是稳定的。void InsertSort(ElemTy

6、pe A,int n)int i,j;for(i=2;i=n;i+)if(Ai.keyAi-1.key)A0=Ai;for(j=i-1;A0.keyAj.key;-j)Aj+1=Aj;Aj+1=A0; 分析排序算法稳定性首先要熟悉算法的流程来判断，当结果不明显时可以尝试用具体例子手动模拟过程来得出结论本节内容插入类排序王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM插入类排序插入类排序就是在一个有序的序列中，插入一个新的关键字，直到所有的关键字都插入形成一个有序的序列。上一节说的直接插入排序就是一种插入类排序。插入类排序还包括折半插入排序和希尔排序。王道考研/CSKAOYA

7、N.COM折半插入排序直接插入排序是每次边比较然后边移动元素，直到找到插入的位置。折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。下标1234567值5132739455272插入25第次：i=1,j=7,2539,所以修改j=3,i不变。第次：i=1,j=3,1325,所以修改j=2,i不变。此时i=3j=2 查找结束，所以25应该插入到13和27之间，也就是将13后面的元素都向后移动一位，腾出空位给25。王道考研/CSKAOYAN.COM折半插入排序分析下标12345678值513252739455272插入25下标1234

8、567值5132739455272i=3,j=2插入位置为j+1王道考研/CSKAOYAN.COM折半插入排序分析void InsertSort(ElemType A,int n)int i,j,low,high,mid;for(i=2;i=n;i+)/i记录的是待插入的元素下标，也就是说i-1之前的元素都是有序的A0=Ai; /保存待插入的值low=1;high=i-1; while(lowA0.key) high=mid-1; else low=mid+1; /找到了待插入的位置 接下来从后往前依次后移元素腾出位置for(j=i-1;j=high+1;-j)Aj+1=Aj;Ahigh+1=

9、A0;/因为此时high指向的是待插入位置的前一位王道考研/CSKAOYAN.COM折半插入排序分析折半插入排序相比直接插入排序只是在寻找待插入位置时比较的次数减少(不是一个一个比较)，每个待插入元素比较的次数大约在log2n(折半查找判定树),所以n个元素比较操作的时间复杂度为O(nlog2n)。比较次数和表的初始状态无关,因为比较次数实际是和折半的次数有关系，只要满足low=1;dk=dk/2) /初始增量为总长度的一半，之后依次除2且向下取整， /且最后一次要为1for(i=dk+1;i=n;+i)if(Ai.key0&A0.key=1;dk=dk/2) /初始增量为总长度的一半，之后依

10、次除2且向下取整， /且最后一次要为1for(i=dk+1;i=n;+i)if(Ai.key0&A0.keyAj.key; j-=dk) /待插入关键字之前以dk为增量的关键字只要比待插入关键字大的都往后移动dk位Aj+dk=Aj;Aj+dk=A0; /找到了待插入的位置，就将待插入关键字插入这个位置王道考研/CSKAOYAN.COM希尔排序分析void ShellSort (ElemType A,int n)/对顺序表作希尔插入排序，本算法和直接插入排序相比，作了以下修改：/1.前后记录位置的增量是dk，不是1/2.r0只是暂存单元，不是哨兵，当j=1;dk=dk/2) /初始增量为总长度的

11、一半，之后依次除2且向下取整for(i=dk+1;i=n;+i)if(Ai.key0&A0.keyAi），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，这样最多做n-1趟冒泡就能把所有元素排好序。12 52 19452345 92 24 56 90王道考研/CSKAOYAN.COM冒泡排序void BubbleSort(ElemType A,int n)for(i=0;ii;j-)/一趟冒泡过程if(Aj-1.keyAj.ke

12、y)/如果前面的元素比后面的大，则需要做交换ElemType temp=Aj-1.key; Aj-1.key=Aj.key; Aj.key=temp;flag=true; /发生了数据交换 修改标志位if(flag=false)return ; /本趟遍历后没有发生交换，说明表已经有序王道考研/CSKAOYAN.COM冒泡排序分析void BubbleSort(ElemType A,int n)for(i=0;ii;j-)/一趟冒泡过程if(Aj-1.keyAj.key)/如果前面的元素比后面的大，则需要做交换ElemType temp=Aj-1.key; Aj-1.key=Aj.key; A

13、j.key=temp;flag=true; /发生了数据交换 修改标志位if(flag=false)return ; /本趟遍历后没有发生交换，说明表已经有序空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)王道考研/CSKAOYAN.COM冒泡排序分析void BubbleSort(ElemType A,int n)for(i=0;ii;j-)/一趟冒泡过程if(Aj-1.keyAj.key)/如果前面的元素比后面的大，则需要做交换ElemType temp=Aj-1.key; Aj-1.key=Aj.key; Aj.key=temp;flag=true; /发生了数据

14、交换 修改标志位if(flag=false)return ; /本趟遍历后没有发生交换，说明表已经有序稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。王道考研/CSKAOYAN.COM快速排序快速排序是一种基于分治法的排序方法。分治法：第一步首先将原问题分解成若干个子问题，这个子问题只是原问题较小规模的实例。第二步将解决这些子问题，递归地求解各子问题。递归的边界就是问题规模足够小的时候，可以直接求解。每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。pivot=46ij

15、j从右向左扫描找第一个比46小的元素，然后替换掉i所指元素46381945559224469024i从左向右扫描找第一个比46大的元素,然后替换掉j所指的元素55j继续向左扫描找第一个比46小的元素，发现i和j接触。则这趟快速排序结束。pivot=46243819454692554690比46小比46大接下来分别对比46小的序列部分和比46大的序列部分进行快排。王道考研/CSKAOYAN.COM快速排序int Partition(ElemType A,int low,int high) /low是当前待排序的序列起始下标，high是末尾下标ElemType pivot=Alow;/第一个元素作

16、为枢轴while(lowhigh)while(low=pivot) -high;/先从末尾往前找到第一个比枢轴小的元素Alow=Ahigh; /用high的元素替换low的元素while(lowhigh&Alow=pivot) +low; /再从开头往后找到第一个比枢轴大的元素Ahigh=Alow; /用low的元素替换high的元素Alow=pivot;/枢轴元素存放到最终位置return low; /返回存放枢轴的最终位置避免完全顺序的序列出现数组下溢12 24 36 48 60lowhigh王道考研/CSKAOYAN.COM快速排序分析void QuickSort(ElemType A,

17、int low,int high)if(lowhigh) /low和high值要合法int pivotpos=Partition(A,low,high);QuickSort(A,low,pivotpos-1); /分治递归左半部分QuickSort(A,pivotpos+1,high); /分治递归右半部分时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。 最坏情况下时间复杂度为O(n2)，待排序序列越有序，算法效率越低。递归复杂度的表达式：T(n) = aT(n/b) + f(n)n/b是子问题的大小，比如快排每次划分子问题之后的大小，a是子问题大小的数量

18、，f(n)是分解问题和合并问题所需要的时间1)快速排序最优的情况就是每一次Partition取到的元素都刚好平分整个数组 即a=b=2 f(n)=O(n)=(n) 根据主定理的第二种情况T(n)=O(nlogn)王道考研/CSKAOYAN.COM快速排序分析void QuickSort(ElemType A,int low,int high)if(lowhigh) /low和high值要合法int pivotpos=Partition(A,low,high);QuickSort(A,low,pivotpos-1); /分治递归左半部分QuickSort(A,pivotpos+1,high);

19、/分治递归右半部分时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。 最坏情况下时间复杂度为O(n2)，待排序序列越有序，算法效率越低。递归复杂度的表达式：T(n) = aT(n/b) + f(n)n/b是子问题的大小，比如快排每次划分子问题之后的大小，a是子问题大小的数量，f(n)是分解问题和合并问题所需要的时间2)快速排序最坏的情况就是每一次Partition取到的元素在一端， 即T(n)=T(n-1)+T(0)+f(n)=T(n-1)+f(n)=T(n-2)+f(n)+f(n-1)=f(1)+f(2)+f(n)（等差数列）=O(n2)王道考研/CSKA

20、OYAN.COM快速排序分析void QuickSort(ElemType A,int low,int high)if(lowhigh) /low和high值要合法int pivotpos=Partition(A,low,high);QuickSort(A,low,pivotpos-1); /分治递归左半部分QuickSort(A,pivotpos+1,high); /分治递归右半部分时间复杂度：最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。 最坏情况下时间复杂度为O(n2)，待排序序列越有序，算法效率越低。第一次low=1,high=6,Partition得到pi

21、votpos=1第二次Partition 得到pivotpos=2下标123456值123456相当于每次都是将待排序列划分为1个关键字和剩余其他关键字，n个关键字需要划分n-1次，每次时间复杂度为O(n)，所以最坏情况下时间复杂度为O(n2)王道考研/CSKAOYAN.COM快速排序分析void QuickSort(ElemType A,int low,int high)if(lowhigh) /low和high值要合法int pivotpos=Partition(A,low,high);QuickSort(A,low,pivotpos-1); /分治递归左半部分QuickSort(A,pi

22、votpos+1,high); /分治递归右半部分空间复杂度：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 log2(n+1)(每次partition都很均匀)递归树的深度O(logn)最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；稳定性：快速排序是不稳定的，是因为存在交换关键字。对于5 2 2一趟快速排序之后2 2 5 而且序列有序了所以最终也是2 2 5 本节内容选择类排序王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM选择类排序王道考研/CSKAOYAN.COM简单选择排序

23、void SelectSort(ElemType A,int n)for(i=0;in-1;i+) /依次从后面序列中选择当前最小的元素作为第i个元素 最后一个元素不需要排序 min=i; /min存的是当前最小元素所在下标，初值设为第i个 for(j=i+1;jn;j+) /从第i个元素往后找，一直要找到最后一个元素 if(AjAmin) min=j; /如果这个值更小，则更新min值为这个更小的元素所在下标 if(min!=i) /如果第i个元素不是剩下元素最小的，则和最小的进行交换 ElemType temp=Ai; Ai=Amin; Amin=temp; 下标0123456789关键字

24、15521730224567123320王道考研/CSKAOYAN.COM简单选择排序算法分析void SelectSort(ElemType A,int n)for(i=0;in-1;i+) /依次从后面序列中选择当前最小的元素作为第i个元素 最后一个元素不需要排序 min=i; /min存的是当前最小元素所在下标，初值设为第i个 for(j=i+1;jn;j+) /从第i个元素往后找，一直要找到最后一个元素 if(AjAmin)min=j; /如果这个值更小，则更新min值为这个更小的元素所在下标 if(min!=i) /如果第i个元素不是剩下元素最小的，则和最小的进行交换 ElemTyp

25、e temp=Ai; Ai=Amin; Amin=temp; 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)时间复杂度：关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。 当i=0,内层循环执行n-1次，当i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n2)王道考研/CSKAOYAN.COM简单选择排序算法分析void SelectSort(ElemType

26、A,int n)for(i=0;in-1;i+) /依次从后面序列中选择当前最小的元素作为第i个元素 最后一个元素不需要排序 min=i; /min存的是当前最小元素所在下标，初值设为第i个 for(j=i+1;jn;j+) /从第i个元素往后找，一直要找到最后一个元素 if(AjAmin)min=j; /如果这个值更小，则更新min值为这个更小的元素所在下标 if(min!=i) /如果第i个元素不是剩下元素最小的，则和最小的进行交换 ElemType temp=Ai; Ai=Amin; Amin=temp; 稳定性：不稳定 原因就在于交换部分会打破相对顺序对于5 5 2i=0，min=2,

27、交换5和22 5 55和5的顺序发生了变化王道考研/CSKAOYAN.COM堆排序什么是堆？堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。9570905060304030405060709095大顶堆小顶堆王道考研/CSKAOYAN.COM堆排序什么是堆排序？我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这

28、个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。所以堆排序最重要的操作就是将无序序列调节成一个堆。王道考研/CSKAOYAN.COM堆排序12 52 19 45 23 45 92（以大顶堆排序为例） 12521923454592原始序列建堆:对初始序列的完全二叉树调整成一个大顶堆12521945234592调整方法：二叉树由下至上由右至左(数组的下标由大到小)，检查每个结点是否满足大顶堆的要求，如果不满足进行调整。45 23 45 92 四个结点都是叶子结点，不需要调整194545且23 不需要调整王道考研/CSKAOYAN.COM堆排序12 52 19

29、 45 23 45 92 12529223454519建堆:对初始序列的完全二叉树调整成一个大顶堆12529245234519调整方法：二叉树由下至上由右至左(数组的下标由大到小)，检查每个结点是否满足大顶堆的要求，如果不满足进行调整。125292 要用92交换12王道考研/CSKAOYAN.COM堆排序12 52 19 45 23 45 92 92521223454519建堆:对初始序列的完全二叉树调整成一个大顶堆92521245234519调整方法：二叉树由下至上由右至左(数组的下标由大到小)，检查每个结点是否满足大顶堆的要求，如果不满足进行调整。121912 不需要调整，52也不需要19

30、4512 不需要调整，52也不需要194552 需要将结点19和52交换192312 不需要调整，52也不需要194552 需要将结点19和52交换19231时，结点i的双亲结点编号为i/2，即当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。当2iN时，结点i的左孩子编号为2i，否则无左孩子。当2i+1N时，结点i的右孩子编号为2i+1，否则无右孩子。设最后一个结点编号为N，N等于二叉树中结点数量，它肯定是叶子结点。所以第一个可能需要调整的非叶结点的下标为 N/2 从它的左孩子开始检查，它的左孩子下标为 N/2

31、 *2如果发生交换，下一轮检查交换过的结点的左右孩子123456712521923454592 7/2 =3，即下标为3的位置存储的是第一个可能需要调整的非叶结点。它的左孩子下标为3*2=6第一个可能需要调整非叶结点第一个比较大小的结点王道考研/CSKAOYAN.COM堆排序算法void BuildMaxHeap(ElemType A,int len)for(int i=len/2;i0;i-) AdjustDown(A,i,len); /由数组下标高处往低处 从第一个可能需要调整的非叶结点 / 开始检查，直到根结点(注意根结点下标不是0，是从1开始存储)void AdjustDown(Ele

32、mType A,int k,int len) /A是存储堆的数组,k是需要检查的结点下标,len是堆中结点个数A0=Ak; /A0暂存这个需要检查的结点值for(i=2*k;i=len;i*=2)/从这个结点的左孩子开始往下比较， / 如果发生交换，对交换过的结点继续和它的孩子比较if(ilen&Ai=Ai) break;/如果这个结点的值不小于它的较大孩子结点值 则不需要交换else Ak=Ai;/如果这个结点的值小于它的较大孩子 /结点值则将较大的孩子结点值赋值给该结点k=i;/i赋值给k也就是从i开始继续往下检查 直到所有结点检查结束Ak=A0;/检查到最后k的值就是最后一轮交换过的结点

33、位置下标 将该结点换过去王道考研/CSKAOYAN.COM堆排序算法void BuildMaxHeap(ElemType A,int len)for(int i=len/2;i0;i-) AdjustDown(A,i,len); void AdjustDown(ElemType A,int k,int len) A0=Ak; for(i=2*k;i=len;i*=2) if(ilen&Ai=Ai) break;else Ak=Ai;k=i;Ak=A0;12521945234592123456712521923454592len/2= 7/2 =3第一次调用AdjustDown，k=3 ，A0=

34、A3=19,i=2*k=6，A6=45A7=92,i=6+1=7 A0=197 跳出for循环 A3=A0=19王道考研/CSKAOYAN.COM堆排序算法void HeapSort(ElemType A,int len)BuildMaxHeap(A,len);/初始建堆for(i=len;i1;i-)/n-1趟的交换和建堆过程/输出堆顶元素(和堆底元素交换) ElemType temp=Ai; Ai=A1; A1=temp; printf(Ai);AdjustDown(A,1,i-1);/把剩余的i-1个元素整理成堆空间复杂度： 堆排序只需要在交换结点的时候需要额外存储空间来辅佐， 所以空间

35、复杂度为O(1)时间复杂度： 堆排序的总时间可以分为建堆部分+n-1次向下调整堆建堆部分:时间复杂度为O(n)12521923454592王道考研/CSKAOYAN.COM堆排序算法void HeapSort(ElemType A,int len)BuildMaxHeap(A,len);/初始建堆for(i=len;i1;i-)/n-1趟的交换和建堆过程Swap(Ai,A1);/输出堆顶元素(和堆底元素交换)AdjustDown(A,1,i-1);/把剩余的i-1个元素整理成堆12521923454592假如有N个结点，那么高度为H= log2(n+1) ，叶子结点的每个父结点最多只需要下调1

36、次，倒数第二层的父结点最多只需要下调2次，根结点最多需要下调H次，而叶子结点的父结点共有2 H-1个,倒数第二层共有2H-2,根结点只有1个，所以最多需要调整次数为s = 1 * 2H-1 + 2 * 2H-2 + . + (H-1) * 21 + H * 20 =2N - 2 - log2(n+1) 王道考研/CSKAOYAN.COM堆排序算法void HeapSort(ElemType A,int len)BuildMaxHeap(A,len);/初始建堆for(i=len;i1;i-)/n-1趟的交换和建堆过程Swap(Ai,A1);/输出堆顶元素(和堆底元素交换)AdjustDown(

37、A,1,i-1);/把剩余的i-1个元素整理成堆调堆部分:一次调堆从上至下最坏情况走得路径是从根结点到叶子结点，完全二叉树的高度为log2(n+1) ，所以时间复杂度为O(log2n)那么n-1个顶点时间复杂度为O(nlog2n)12521923454592王道考研/CSKAOYAN.COM堆排序算法void HeapSort(ElemType A,int len)BuildMaxHeap(A,len);/初始建堆for(i=len;i1;i-)/n-1趟的交换和建堆过程Swap(Ai,A1);/输出堆顶元素(和堆底元素交换)AdjustDown(A,1,i-1);/把剩余的i-1个元素整理成

38、堆时间复杂度： 堆排序的总时间可以分为建堆部分+n-1次向下调整堆 堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)12521923454592王道考研/CSKAOYAN.COM堆排序算法void HeapSort(ElemType A,int len)BuildMaxHeap(A,len);/初始建堆for(i=len;i1;i-)/n-1趟的交换和建堆过程Swap(Ai,A1);/输出堆顶元素(和堆底元素交换)AdjustDown(A,1,i-1);/把剩余的i-1个元素整理成堆122稳定性：右图初始序列为1 2 2 由于2在左孩子位置 第一次交换之后2换到了堆顶 所以

39、2最终排好的位置在最后 也就是1 2 2 两个2的位置发生了变化，所以堆排序不稳定本节内容归并排序王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM归并排序假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 n/2个长度为2或1的有序表；再两两归并，如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。49 38 65 97 76 13 27首先将整个序列的每个关键字看成一个单独的有序的子序列两两归并，49和38归并成38 49 ，65和97归并成65 97，76和13归并成13 76，27没有归并对象两两归并，

40、38 49和65 97归并成38 49 65 97，13,76和27归并成13 27 76两两归并，38 49 65 97和13 27 76归并成13 27 38 49 65 76 97王道考研/CSKAOYAN.COM归并排序ElemType *B=(ElemType *)malloc(n+1)*sizeof(ElemType); /辅助数组B(动态分配内存)void Merge(ElemType A,int low,int mid,int high)/表A的两段Alowmid和Amid+1high各自有序，将它们合并成一个有序表for(int k=low;k=high;k+)Bk=Ak;/

41、将A中所有元素复制到B中for(int i=low,j=mid+1,k=i;i=mid&j=high;k+) k是归并之后数组的下标计数器if(Bi=Bj) /比较B的左右两段中的元素Ak=Bi+;/将较小值复制到A中elseAk=Bj+;while(i=mid)Ak+=Bi+;/若第一个表未检测完，直接将剩下的部分复制过来while(j=high)Ak+=Bj+;/若第二个表未检测完，直接将剩下的部分复制过来王道考研/CSKAOYAN.COM归并排序void MergeSort(ElemType A,int low,int high)if(lowhigh)int mid=(low+high)

42、/2;/从中间划分两个子序列MergeSort(A,low,mid);/对左侧子序列进行递归排序MergeSort(A,mid+1,high); /对右侧子序列进行递归排序Merge(A,low,mid,high);/归并一共n个元素12345nhhhhhh2h2hMerge()所以n个元素调用 n/2h次王道考研/CSKAOYAN.COM归并排序分析void MergeSort(ElemType A,int low,int high)if(lowhigh)int mid=(low+high)/2;/从中间划分两个子序列MergeSort(A,low,mid);/对左侧子序列进行递归排序Mer

43、geSort(A,mid+1,high); /对右侧子序列进行递归排序Merge(A,low,mid,high);/归并一共n个元素第趟Merge：子序列长度为2，所以有n/2对子序列，每个子序列需要执行1次Merge。Merge时间复杂度为子序列长度之和 即2所以第趟merge的时间复杂度为O(n/2*2)=O(n)49 38 65 97 76 13 27 45 n/2对第趟Merge：子序列长度为4，所以有n/4对子序列，每个子序列需要执行1次Merge，Merge时间复杂度为子序列长度之和 即4,所以第趟merge的时间复杂度为O(n/4*4)=O(n)38 49 65 97 13 76

44、 27 45 n/4对时间复杂度：王道考研/CSKAOYAN.COM归并排序分析一共n个元素第趟归并：子序列长度为2，所以有n/2对子序列，每个子序列需要执行1次Merge。Merge时间复杂度为子序列长度之和 即2所以第趟merge的时间复杂度为O(n/2*2)=O(n)49 38 65 97 76 13 27 45 n/2对第趟归并：子序列长度为4，所以有n/4对子序列，每个子序列需要执行1次Merge，Merge时间复杂度为子序列长度之和 即4,所以第趟merge的时间复杂度为O(n/4*4)=O(n)38 49 65 97 13 76 27 45 n/4对第k趟归并：子序列长度为2k,

45、所以有n/2k对子序列当n/2k=1时，k=log2n 此时需要归并的两个子序列长度为n/2，只需要一次Merge就能实现整个序列有序。所以一共执行了k=log2n趟排序，每趟排序的时间复杂度都是O(n)所以整个归并排序的时间复杂度为O(nlog2n)王道考研/CSKAOYAN.COM归并排序分析空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)稳定性：1342345lowmidmid+1high归并前3在3前面1233445lowhigh归并后3依然在3前面本节内容基数排序王道考研/CSKAOYAN.COM王道考研/CSKAOYAN

46、.COM基数排序基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。53, 3, 542, 748, 14, 214, 154, 63, 616桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616桶实际是一个队列，先进先出(从桶的上面进，下面出)053003542748014214154063616第一次“分配”

47、（队列从上入队）王道考研/CSKAOYAN.COM基数排序桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9053003542748014214154063616第一次“收集” （队列从下出队）542053003063014214154616748桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9第二次“分配”（队列从上入队）542053003063014214154616748王道考研/CSKAOYAN.COM基数排序003014214616542748053154063桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9542053003063014214154616748第二次“收集”（队列从下出队）桶0桶1桶2桶3桶

48、4桶5桶6桶7桶8桶9第三次“分配” （队列从上入队）003014214616542748053154063王道考研/CSKAOYAN.COM基数排序桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9003014214616542748053154063第三次“收集” （队列从下出队）003014053063154214542616748由于关键字现在三个数位都排列有序，所以整个关键字序列都排列有序。王道考研/CSKAOYAN.COM基数排序性能分析空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字

49、的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10时间复杂度：需要进行关键字位数d次分配和收集，一次分配需要将n个关键字放进各个队列中，一次收集需要将r个桶都收集一遍。所以一次分配和一次收集时间复杂度为O(n+r)。d次就需要O(d(n+r)的时间复杂度。稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。王道考研/CSKAOYAN.COMMSD53, 3, 542, 748, 14, 214, 154, 63, 616桶0桶1桶2桶3桶4桶5桶6桶7桶8桶905300354274801

50、4214154063616对桶中关键字个数不为1的桶递归排序王道考研/CSKAOYAN.COMMSD桶0053003014063桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9003053014063对次高位进行分配王道考研/CSKAOYAN.COMMSD桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9003053014063此时各个桶中都只有一个关键字，递归结束，收集各桶返回到上一层。此时桶中是这个样子。桶0桶1桶2桶3桶4桶5桶6桶7桶8桶9003014542748053214154063616王道考研/CSKAOYAN.COMMSD桶0桶1桶2桶3桶4桶5桶6桶7桶8桶90030145427480532

51集各桶：得到有序序列 003 014 053 063 154 214 542 616 748本节内容外部排序王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM外部排序截止目前学习过的所有排序算法，都是建立在计算机的内存上进行。由于内存的大小限制，前面所学的排序算法都是针对数据量不是特别大的情况。所以这些排序都属于内部排序。但是很多时候，需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件拷贝进内存中进行排序。解决办法：需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的

52、交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。王道考研/CSKAOYAN.COM外部排序多路归并算法12454376499612117内存三路归并有序的归并段王道考研/CSKAOYAN.COM外部排序多路归并算法12454376499612117内存王道考研/CSKAOYAN.COM外部排序多路归并算法12454376499612117内存王道考研/CSKAOYAN.COM外部排序多路归并算法12454376499612117内存通过多路归并，就实现了在较小的内存容量完成大规模的数据排序。一开始的这些有序的归并段如何得到？当然可以以单个数据为有序，

53、然后一个一个数据调入内存中进行排序得到一些归并段。但是带来的开销会非常大王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3172105内存输出有序归并段：剩余序列：44，10，12，56，32，29王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3172105内存输出有序归并段：剩余序列：44，10，12，56，32，2905王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3172

54、144内存输出有序归并段：剩余序列：10，12，56，32，2905王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3172144内存输出有序归并段：剩余序列：10，12，56，32，290517王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3102144内存输出有序归并段：剩余序列：12，56，32，290517王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3102144内存

55、输出有序归并段：剩余序列：12，56，32，29051721王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3101244内存输出有序归并段：剩余序列：56，32，29051721王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3101244内存输出有序归并段：剩余序列：56，32，2905172144王道考研/CSKAOYAN.COM置换-选择排序初始序列：17，21，05，44，10，12，56，32，29内存大小：3101256内存输出有序归并段：剩余序列：32，2905172144