- 什麼是合并排序：
合并排序就是将兩個或多個有序表合并成一個有序表，将兩個有序表合并成一個有序表稱為二路合并
- 算法描述 ：
二路合并排序的基本思想是：對于兩個有序表合并，初始時， 把含有n個結點的待排序序列看作有n個長度為1的有序子表所組成，将它們依次兩兩合并，得到長度為2的若幹有序子表，再對這些子表進行兩兩合并，一直重複到長度為n，排序完成。
- 合并排序過程：
初始序列：
 |
二路合并排序需要較大的輔助空間，輔助空間的大小與待排序序列一樣多。
(1)将14個原資料看成14個長度為1的有序表（隻有一個資料，肯定是有序的）
(2)将14個有序表兩兩合并，即将1,2合并3,4合并.....如果後面有單獨一個元素的，就單獨放在那裡，直接進入下一遍合并
 |
(3)經過第一遍的合并，得到長度為2的有序表序列，再将這些長度為2的有序表序列進行兩兩合并。
| |
(4)經過第二遍合并之後，得到長度為4的有序表的序列，再将這些長度為4的有序表進行兩兩合并。
| |
(5) 經過上面的合并，得到長度為8的有序表，再将這些長度為8的有序表進行兩兩合并。
| |
- 合并相鄰有序表 ：
如果需合并的兩個有序表分别儲存于數組A中，其中一個序列儲存在下标s~m的數組元素中，另一個序列儲存在下标從m+1~n的數組元素中。合并把結果儲存在數組R中。用變量i,j分别指向兩個系列中需要比較的元素，變量k指向數組R中的序号，表示下一個要儲存的資料的位置。
(1) 取第1個系列的第i個元素A[i]，與第2個系列的第1個元素比較A[j]。
(2) 若A[i]<=A[j]，則将A[i]複制到R[k]中，使i和k分别增加1.
(3)若A[i]>A[j]，則将A[j]複制到R[k]中，使j和k分别增加1
(4)重複步驟1~3，直到一個序列複制完為止。
(5)将另一個序列中比較的資料複制到R的剩餘位置。
| //a[low...mid]和a[mid+1,high] 而b[low...high] void Merge(int a[],int b[],int low,int mid,int high){ int i=low; int j=mid+1; int k=low; while(i<=mid && j<=high){ if(a[i]<=a[j]){ b[k++]=a[i++]; }else{ b[k++]=a[j++]; } } private static void merge(int a[],int temp[],int low,int mid,int high){ int i=low; int j=mid+1; int k=0; while(i<=mid && j<=high) { if(a[i]<=a[j]) { temp[k++]=a[i++]; }else { temp[k++]=a[j++]; } } while(i<=mid) { temp[k++]=a[i++]; while(j<=high) { temp[k++]=a[j++]; k = 0; // 将temp中的元素全部拷貝到原數組中 while (low <= high) { a[low++] = temp[k++]; } |
- 歸并排序：
(1) 二路歸并排序将a[low...high]中的記錄歸并排序後放入temp[low...high]中。當序列長度等于1時，遞歸結束，否則：
a) 将目前序列一分為二，求出分裂點mid=(low+high)/2
b) 對子序列a[low..mid]遞歸，進行歸并排序，結果放入temp[low...mid]
c) 對子序列a[mid+1,high],進行歸并排序，結果放入temp[mid+1,high]
d) 調用Merge将有序的兩個子序列a[low..mid]與a[mid+1,high]歸并為一個有序的序列temp[low...high]
| /** * sort */ public static void sort(int a[],int temp[],int low,int high) { if(low<high) { int mid=(low+high)/2; sort(a,temp,low,mid); sort(a,temp,mid+1,high); merge(a,temp,low,mid,high); |
- 算法執行個體：
| public class MergeSort { /** * 相鄰有序子序列進行合并 * a[low...mid] a[mid+1,high] */ private static void merge(int a[],int temp[],int low,int mid,int high){ int k=0; while(i<=mid && j<=high) { if(a[i]<=a[j]) { temp[k++]=a[i++]; }else { temp[k++]=a[j++]; while(i<=mid) { while(j<=high) { k = 0; // 将temp中的元素全部拷貝到原數組中 while (low <= high) { a[low++] = temp[k++]; public static void sort(int a[],int temp[],int low,int high) { if(low<high) { int mid=(low+high)/2; sort(a,temp,low,mid); sort(a,temp,mid+1,high); merge(a,temp,low,mid,high); public static void sort(int []arr){ int []temp = new int[arr.length];//在排序前，先建好一個長度等于原數組長度的臨時數組，避免遞歸中頻繁開辟空間 sort(arr,temp,0,arr.length-1); } public static void main(String[] args) { int arr[]= {56,41,26,32,55,75,2,63,12,19,58,77,34,95}; sort(arr); System.out.println("排序結果："+Arrays.toString(arr)); /* 測試，合并有序子序列 int arr[]= {1,3,5,2,4,6}; int temp[]=new int[arr.length]; merge(arr, temp, 0, 2, arr.length-1); System.out.println("排序結果："+Arrays.toString(temp)); */ |