归并排序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