歸并排序
所謂歸并，就是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表豪嚎。如下圖所示悼瘾，有兩個(gè)已經(jīng)排好序的有序表A[1]~A[n]和B[1]~B[m]（在圖中只給出了它們的關(guān)鍵字）捆憎，通過(guò)歸并把它們合成一個(gè)有序表C[1]~C[m+n]握恳。
基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列完丽，每個(gè)子序列是有序的恋技。然后再把有序子序列合并為整體有序序列。
兩路歸并算法的C++描述
在這個(gè)算法中舰涌，兩個(gè)待歸并的有序表首尾相接存放在數(shù)組sourceTable.Arr[]中猖任，其中第一個(gè)表的下標(biāo)范圍是從 left 到 mid，另一個(gè)表的下標(biāo)范圍從 mid+1 到 right瓷耙。歸并后得到的新有序表存放在另一個(gè)輔助數(shù)組中 mergedTable.Arr[] 中朱躺，其下標(biāo)范圍從 left 到 right。
template <class Type>
void merge ( sortlist<Type> & sourceTable, sortlist <Type> & mergedTable,
const int left, const int mid, const int right ) {
int i = left, j = mid+1, k =left;//指針初始化
while ( i <= mid && j <= right ){
if ( sourceTable.Arr[i].getKey() <= sourceTable.Arr[j].getKey()){
mergedTable.Arr[k] = sourceTable.Arr[i];
i++;
k++;
} else {
mergedTable.Arr[k] = sourceTable.Arr[j];
j++;
k++;
}
}
if ( i <= mid ){
for ( int p = k, q = i; q <= mid; p++, q++ ){
mergedTable.Arr[p] = sourceTable.Arr[q];
}
} else {
for ( int p = k, q = j; q <= right; p++, q++){
mergedTable.Arr[q] = sourceTable.Arr[p];
}
}
}
兩路歸并排序
兩路歸并排序就是利用兩路歸并算法進(jìn)行排序搁痛。
其算法基本思想是：假設(shè)初始排序表有n個(gè)數(shù)據(jù)元素长搀，首先把它看成是長(zhǎng)度為1的首尾相接的n個(gè)有序子表(以后稱它們?yōu)闅w并項(xiàng))，先做兩兩歸并鸡典，得 ?n/2? 個(gè)長(zhǎng)度為2的歸并項(xiàng)(如果n為奇數(shù)源请，則最后一個(gè)歸并項(xiàng)的長(zhǎng)度為1)；再做兩兩歸并彻况，……谁尸，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為n的有序序列纽甘。
一趟歸并的算法描述如下
template <class Type>
void MergePass ( sortlist<Type> & sourceTable,
sortlist<Type> & mergedTable, const int len ) {
int i =0;
while ( i+2*len <= CurrentSize-1 ){
merge ( sourceTable, mergedTable, i, i+len-1, i+2*len-1);
i += 2 * len;
}
if ( i+len <= CurrentSize-1 ){
merge ( sourceTable, mergedTable,i, i+len-1, CurrentSize-1 );
}else{
for ( int j=i; j <= CurrentSize-1; j++ ){
mergedTable.Arr[j] = sorceTable.Arr[j];
}
}
}
兩路歸并排序算法描述如下
template <class Type>
void MergeSort ( sortlist<Type> & table ) {
sortlist<Type> & tempTable;
int len = 1;
while ( len < table.CurrentSize ) {
MergePass (table , tempTable, len ); len *= 2;
MergePass (tempTable , list , len ); len *= 2;
}
delete []tempTable;
}
在兩路歸并排序算法中良蛮，函數(shù)MergePass( )做一趟歸并，要調(diào)用merge( )函數(shù) ?n/(2*len)? ≈ O(n/len)次悍赢，而每次merge( )要執(zhí)行比較次數(shù)不超過(guò)2*len-1决瞳，為O(len)，函數(shù)MergeSort( )調(diào)用MergePass( )正好 ?log2n? 次皮胡，所以兩路歸并排序算法總的時(shí)間復(fù)雜度為O(nlog?n)痴颊。
兩路歸并排序占用附加存儲(chǔ)較多蠢棱，需要另外一個(gè)與原待排序數(shù)據(jù)元素?cái)?shù)組同樣大小的輔助數(shù)組，所以其空間復(fù)雜度為O(n）甩栈。 兩路歸并排序是一個(gè)穩(wěn)定的排序方法。
遞歸的歸并排序
在遞歸的歸并排序方法中谤职，首先要把整個(gè)排序表劃分為長(zhǎng)度大致相等的左右兩個(gè)部分允蜈，分別稱之為左子表和右子表，對(duì)這兩個(gè)子表分別進(jìn)行歸并排序（遞歸）蒿柳，然后再把已排好序的這兩個(gè)子表進(jìn)行兩路歸并饶套，得到一個(gè)有序表。
遞歸的歸并排序示例
在遞歸的歸并排序過(guò)程中垒探，如果使用前面給出的兩路歸并算法妓蛮，需要進(jìn)行數(shù)組元素的傳遞，這非常影響歸并的效率圾叼。如果排序表采用鏈表的存儲(chǔ)表示蛤克，可以得到一種有效的歸并排序算法。
在此排序表以靜態(tài)鏈表存儲(chǔ)夷蚊，設(shè)待排序的數(shù)據(jù)元素存放在類型為的靜態(tài)鏈表table中构挤。table.Arr[0]用于表示結(jié)果鏈表的頭結(jié)點(diǎn)。函數(shù)linkListMerge()是將兩個(gè)有序的單鏈表歸并成一個(gè)有序單鏈表的算法惕鼓。
靜態(tài)鏈表上的遞歸歸并排序示例
在靜態(tài)鏈表上實(shí)現(xiàn)兩路歸并的算法描述如下
template <class Type>
int linkListMerge (sortlinklist<Type> &table, const int p, const int q ) {
int k = 0, i = p, j = q;
//初始化指針,其中k為結(jié)果鏈表的尾結(jié)點(diǎn)指針,i筋现、j為搜索指針
while ( i !=-1 && j !=-1 ){
if ( table.Arr[i].getKey()<=table.Arr[j].getKey() ){
table.Arr[k].setLink(i);
k = i;
i = table.Arr[i].getLink( );
}else {
table.Arr[k].setLink(j);
k = j;
j = table.Arr[j].getLink( );
}
}
if (!i){
table.Arr[k].setlink(j);
}else{
table.Arr[k].setLink(i);
}
return table.Arr[0].getLink();
}
遞歸歸并排序算法
template <class Type>
int linkListMergeSort (sortlinklist<Type> &table, const int low, const int high )
{
if ( low >= high ) return low;
int mid = ( low + high ) / 2;
return linkListMerge (table, linkListMergeSort ( table, low, mid ),
linkListMergeSort ( table,mid+1, right ) );
}
在靜態(tài)鏈表上實(shí)現(xiàn)的遞歸歸并排序算法，通過(guò)鏈接指針的修改以實(shí)現(xiàn)數(shù)據(jù)元素接點(diǎn)的邏輯有序鏈接箱歧，因此不需要數(shù)據(jù)元素移動(dòng)矾飞。計(jì)算時(shí)間可以用數(shù)據(jù)元素關(guān)鍵字的比較次數(shù)來(lái)測(cè)量。
算法的遞歸深度為O(log?n)呀邢，所以總的時(shí)間復(fù)雜度為0(nlog?n)洒沦。它也是一種穩(wěn)定的排序方法。
歸并排序的C++實(shí)現(xiàn)
設(shè)兩個(gè)有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：R[low...m]驼鹅，R[m+1...high]微谓，先將它們合并到一個(gè)局部的暫存向量R1(相當(dāng)于輸出堆)中森篷，待合并完成后將R1復(fù)制回R[low...high]中。
合并過(guò)程：
- 設(shè)置i豺型，j和p三個(gè)指針仲智，其初值分別指向這三個(gè)記錄區(qū)的起始位置;
- 合并時(shí)依次比較R[i]和R[j]的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1[p]中;
- 然后將被復(fù)制記錄的指針i或j加1姻氨，以及指向復(fù)制位置的指針p加1钓辆。
- 重復(fù)這一過(guò)程直至兩個(gè)輸入的子文件有一個(gè)已全部復(fù)制完畢(不妨稱其為空)，此時(shí)將另一非空的子文件中剩余記錄依次復(fù)制到R1中即可肴焊。
void Merge(int src[], int des[], int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int k = low;
while( (i <= mid) && (j <= high) ) //將小的放到目的地中
{
if( src[i] < src[j] )
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while( i <= mid ) //若還剩幾個(gè)尾部元素
{
des[k++] = src[i++];
}
while( j <= high ) //若還剩幾個(gè)尾部元素
{
des[k++] = src[j++];
}
}
//每次分為兩路 當(dāng)只剩下一個(gè)元素時(shí)前联，就不需要在劃分。先劃分再歸并娶眷。
void MSort(int src[], int des[], int low, int high, int max)
{
if( low == high ) //只有一個(gè)元素似嗤，不需要?dú)w并，結(jié)果賦給des[low]
{
des[low] = src[low];
}
else //如果多個(gè)元素届宠，進(jìn)行兩路劃分
{
int mid = (low + high) / 2;
int* space = (int*)malloc(sizeof(int) * max);
//遞歸進(jìn)行兩路，兩路的劃分
//當(dāng)剩下一個(gè)元素的時(shí)伤塌，遞歸劃分結(jié)束轧铁，然后開(kāi)始merge歸并操作
if( space != NULL )
{
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high); //調(diào)用歸并函數(shù)進(jìn)行歸并
}
free(space);
}
}
void MergeSort(int array[], int len)
{
MSort(array, array, 0, len-1, len);
}
歸并排序的Java實(shí)現(xiàn)
/*
* 歸并操作(merge)齿风，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作果善。
* 如設(shè)有數(shù)列{6巾陕，202纪他，100茶袒，301，38亡资，8，1}
* 初始狀態(tài)： [6] [202] [100] [301] [38] [8] [1] 比較次數(shù)
* i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
* i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
* i=3 [ 1 6 8 38 100 202 301 ] 4
*/
public class MergeSort {
public static void sort(int[] data) {
int[] temp = new int[data.length];
mergeSort(data, temp, 0, data.length - 1);
}
private static void mergeSort(int[] data, int[] temp, int l, int r) {
int mid = (l + r) / 2;
if (l == r)
return;
mergeSort(data, temp, l, mid);
mergeSort(data, temp, mid + 1, r);
for (int i = l; i <= r; i++) {
temp[i] = data[i];
}
int i1 = l;
int i2 = mid + 1;
for (int cur = l; cur <= r; cur++) {
if (i1 == mid + 1)
data[cur] = temp[i2++];
else if (i2 > r)
data[cur] = temp[i1++];
else if (temp[i1] < temp[i2])
data[cur] = temp[i1++];
else
data[cur] = temp[i2++];
}
}
}
