河池学院：《数据结构》课程电子教案（PPT教学课件）第10章 排序 10.5 归并排序 10.6 基数排序 10.7 各种内排序方法的比较和选择

主要的归并排序方法： 有序段1 有序段2 . 有序段k 新有序段1 有序段1 有序段2 . 有序段k 新有序段2 . . 1/41

1. 排序思路 18 2 20 34 12 32 6 16 1 5 18 2 20 34 12 32 6 16 1 15 2 18 20 34 12 32 6 16 1 15 2 18 20 34 6 12 16 32 1 15 2 6 12 16 18 20 32 34 1 15 1 2 6 12 15 16 18 20 32 34 底 2/41

18 2 20 34 12 32 6 16 1 5 18 2 20 34 12 32 6 16 1 15 第1趟 2 18 20 34 12 32 6 16 1 15 2 18 20 34 6 12 16 32 1 15 2 6 12 16 18 20 32 34 1 15 1 2 6 12 15 16 18 20 32 34 第2趟 第3趟 第4趟 归 并 树 有清晰的趟数（同一趟产生的归并段优先归并） 归并树高度h=log2n+1 归并的趟数=h-1 平 衡 归 并 3/41

2. 排序算法 基础：将两个位置相邻的有序子序列归并为一个有序序列。 有 序 序 列 R[low.high] 有序子序列 R[low.mid] 有序子序列 R[mid+1.high] R[low.high] 4/41

private void Merge(int low,int mid,int high) //R[low.mid]和R[mid+1.high]归并为R[low.high] { RecType[] R1=new RecType[high-low+1]; int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标 while (i<=mid && j<=high) //在第1段和第2段均未扫描完时循环 if (R[i].key<=R[j].key) //将第1段中的元素放入R1中 { R1[k]=R[i]; i++; k++; } else //将第2段中的元素放入R1中 { R1[k]=R[j]; j++; k++; } while (i<=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++; k++; } while (j<=high) //将第2段余下部分复制到R1 { R1[k]=R[j]; j++; k++; } for (k=0,i=low;i<=high;k++,i++) //将R1复制回R中 R[i]=R1[k]; } 空间复杂度为O(high-low+1) 5/41

有序子表长度为len  R[0.n-1]中共分为n/len个有序的子表 段2的尾元素序号i+2len-1<n 是满的（两个段均含len个元素） i+len-1<n-1（或者i+len<n）  剩余两个有序子表 否则说明仅剩余一个有序子表（第2段为空），不趟不参与归并 R[0.len-1] R[len.2len-1] R[2len.3len-1] R[3len.4len-1] 起始i=0 起始i=2len 段1 段2 R[i.i+len-1] R[i+len.i+2len-1] 起始i=i+2len 6/41

private void MergePass(int len) //一趟二路归并排序 { int i; for (i=0;i+2*len-1<n;i=i+2*len) //归并len长的两相邻子表 Merge(i,i+len-1,i+2*len-1); if (i+len<n) //余下两个子表,后者长度小于len Merge(i,i+len-1,n-1); //归并这两个子表 } 7/41

public void MergeSort1() //对R[0.n-1]按递增进行二路归并算法 { for (int len=1;len<n;len=2*len) //进行log2n(取上界)趟归并 MergePass(len); } 8/41

3. 算法分析 二路归并排序中，长度为n的排序表需做log2n趟，对应的归并树高度为 log2n，每趟归并时间为O(n)。 时间复杂度的最好、最坏和平均情况都是O(nlog2n)。 log2n趟 每趟为O(n) 9/41

归并排序过程中每次调用Merge都需要使用局部数组R1，但执行完后其空 间被释放，但最后一趟排序一定是全部n个元素参与归并，所以总的辅助 空间复杂度为O(n)。 18 2 20 34 12 32 6 16 1 15 2 18 20 34 12 32 6 16 1 15 2 18 20 34 6 12 16 32 1 15 2 6 12 16 18 20 32 34 1 15 1 2 6 12 15 16 18 20 32 34 10/41