簡介
歸並排序以O(NlogN)最壞情形時間運行,而所使用的比較次數幾乎是最優的。
這個算法中基本的操作是合並兩個已排序的表。基本的合並算法是取兩個輸入數組A和B,一個輸出數組C,以及3個計數器Actr、Bctr、Cctr,它們初始置於對應數組的開始端。A[Actr]和B[Bctr]中的較小者被拷貝到C中的下一個位置,相關的計數器向前推進一步。當兩個輸入表有一個用完的時候,則將另一個表中剩余部分拷貝到C中。
合並兩個已排序的表的時間顯然是線性的,因為最多進行N-1次比較,其中N是元素的總數。
算法描述:如果N=1,那麼只有一個元素需要排序,否則,遞歸地前將半部分數據和後半部分數據各自歸並排序,得到得到排序後的兩部分數據,然後使用上面描述的合並算法再將這兩部分合並到一起。
分治(divide-and-conquer)策略:它將問題分(divide)成一些小的問題然後遞歸求解,而治(conquer)的階段則將分的階段解得的各答案修補在一起。
實現代碼如下:
/**
* Internal method that makes recursive calls
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
*/
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a,AnyType[] tmpArray,int left,int right) {
if(left<right){
int center = (left+right)/2;
mergeSort(a,tmpArray,left,center);
mergeSort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}
/**
* Mergesort algorithm
* @param a an array of Comparable items
*/
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a){
AnyType[] tmpArray = (AnyType[])new Comparable[a.length];
mergeSort(a,tmpArray,0,a.length-1);
}
/**
* Internal method that merges two sorted halves of a subarray
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param leftPos the left-most index of the subarray
* @param rightPos the index of the start of the second half
* @param rightEnd the right-most index of the subarray
*/
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a,AnyType[] tmpArray,int leftPos,int rightPos,int rightEnd){
int leftEnd = rightPos -1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
//main loop
while(leftPos<=leftEnd && rightPos<=rightEnd){
if(a[leftPos].compareTo(a[rightPos])<=0){
tmpArray[tmpPos++] = a[leftPos++];
}else{
tmpArray[tmpPos++] = a[rightPos++];
}
}
//Copy rest of the first array
while(leftPos<=leftEnd){
tmpArray[tmpPos++] = a[leftPos++];
}
//Copy rest of the right array
while(rightPos<=rightEnd){
tmpArray[tmpPos++] = a[rightPos++];
}
//Copy tmpArray back
for(int i=0;i<numElements;i++,rightEnd--){
a[rightEnd] = tmpArray[rightEnd];
}
}
歸並排序分析
與其它的O(NlogN)排序算法比較,歸並排序的運行時間嚴重依賴於比較元素和在數組(以及臨時數組)中移動元素的相對開銷。這些開銷是和語言相關的。
在Java中,當執行一次泛型排序(使用Comparator)時,進行一次元素比較可能是昂貴的(因為比較可能不容易被內嵌,從而動態調度的開銷可能會減慢執行的速度),但是移動元素則是省時的(因為它們是引用的賦值,而不是龐大對象的拷貝)。它就是標准Java類庫中泛型排序所使用的算法。在Java中,快速排序用作基本類型的標准庫排序。
在C++的泛型排序中,如果對象龐大,那麼拷貝對象可能需要很大開銷,而由於編譯器具有主動執行內嵌優化的能力,因此比較對象常常是相對省時的。C++類庫中通常使用快速排序(Quicksort)。