归并排序10.5基本思路（k路归并）有序段2有序段k有序段1有序段2有序段有序段1新有序段1新有序段2主要的归并排序方法：二路归井排序1/41
主要的归并排序方法： 有序段1 有序段2 . 有序段k 新有序段1 有序段1 有序段2 . 有序段k 新有序段2 . . 1/41
自底向上的二路归并排序10.5.11.排序思路1822034123216165底2616182034123215121812616152034321218203461216321516121618203234152161215161820323422/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
5182034161212326归井树1823461615201232115183412326162201第1趟23418206121516321第2趟61216183215220341第315612161820323421第4平衡归并有清晰的趟数（同一趟产生的归并段优先归并）归并树高度h=[1og2n]+1归并的趟数=h-13/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.排序算法1）二路归井算法基础：将两个位置相邻的有序子序列归并为一个有序序列。R[low..high]有序子序列 R[low..mid]有序子序列 R[mid+1..high]有序序列 R[low..high]4/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]//k是R1的下标，i、j分别为第1、2段的下标int i=low,j=mid+1,k=0while (i<=mid && j<=high)//在第1段和第2段均未扫描完时循环if (R[i].key<=R[j].key)1/将第1段中的元素放入R1中R1[k]=R[i];i++; k++;空间复杂度为o（high-low+1）子else//将第2段中的元素放入R1中R1[k]=R[j];j++; k++;子while (i<=mid)//将第1段余下部分复制到R1 R1[k]=R[i];i++; k++;7//将第2段余下部分复制到R1while (j<=high)( Ri[k]=R[j];j++; k++;}1/将R1复制回R中for (k=o,i=low;i<=high;k++,i++)R[i]=R1[k];75/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
2）一趟二路归井排序有序子表长度为len R[0..n-1]中共分为[n/len]个有序的子表段1段2R[0..len-1]R[len..2len-1]起始i=0R[2len..3len-1]R[3len..4len-1]起始i=2lenI起始=i+2lenR[i..i+len-1]R[i+len..i+2len-1]段2的尾元素序号+21en-1<n是满的（两个段均含1en个元素）i+len-1<n-1（或者i+len<n）剩余两个有序子表否则说明仅剩余一个有序子表（第2段为空），不趟不参与归并6/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
1/一趟二路归并排序private void MergePass(int len)( int i;//归并1en长的两相邻子表for（i=0;i+2*len-1<n;i=i+2*len）Merge(i,i+len-1,i+2*len-1);if(i+len<n)//余下两个子表，后者长度小于len//归并这两个子表Merge(i,i+len-1,n-1);7/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
3）二路归井排序1/对R[0..n-11按递增进行二路归并算法public void MergeSorti()1/进行1og2n（取上界）趟归井for（intlen=1;len<n;len=2*len）MergePass(len);8/41
public void MergeSort1() //对R[0.n-1]按递增进行二路归并算法 { for (int len=1;len<n;len=2*len) //进行log2n(取上界)趟归并 MergePass(len); } 8/41
算法分析3.1二路归并排序中，长度为n的排序表需做1og,n趟，对应的归并树高度为[1og2nl，每趟归并时间为o(n)。每趟为o(n)「1og2n]趟时间复杂度的最好、最坏和平均情况都是o(nlog2n)。9/41
3. 算法分析 二路归并排序中，长度为n的排序表需做log2n趟，对应的归并树高度为 log2n，每趟归并时间为O(n)。 时间复杂度的最好、最坏和平均情况都是O(nlog2n)。 log2n趟 每趟为O(n) 9/41
归并排序过程中每次调用Merge都需要使用局部数组R1，但执行完后其空间被释放，但最后一趟排序一定是全部n个元素参与归并，所以总的辅助空间复杂度为o(n)。1822034123216156182034123261615134218206121632151216618203234151215161820343210/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