Posted on 2012-11-25 21:23
hoshelly 閱讀(3764)
評論(0) 編輯 收藏 引用 所屬分類:
DS && Algorithm
歸并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
例如，有數(shù)列{6，202，100，301，38，8，1}
1. 剛開始的分組如下：
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 比較次數(shù)為3次
2. 第二次，兩兩分組合并
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 比較次數(shù)為4
3. 第三次，繼續(xù)合并
i=3 [ 1 6 8 38 100 202 301 ] 比較次數(shù)為4
總計的比較次數(shù)為11次
歸并排序具體工作原理如下（假設(shè)序列共有n個元素）：
1. 將序列每相鄰兩個數(shù)字進行歸并操作，形成floor(n / 2)個序列，排序后每個序列包含兩個元素
2. 將上述序列再次歸并，形成floor(n / 4)個序列，每個序列包含四個元素
3. 重復(fù)步驟2，直到所有元素排序完畢
歸并操作的過程如下：
1. 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
2. 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
3. 比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置
4. 重復(fù)步驟3直到某一指針達到序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
自底向上歸并，如圖所示：
遞歸實現(xiàn)代碼：
#include <iostream>
using namespace std;
void merge(int*arr, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for(int i = 0; i < n1; i++)
{
L[i] = arr[p + i];
}
for(int j = 0; j < n2; j++)
{
R[j] = arr[q + j + 1];
}
int i = 0;
int j = 0;
int k = p;
while((i < n1) && (j < n2))
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
if (i < n1)
{
for(; i < n1; i++, k++)
{
arr[k] = L[i];
}
}
if (j < n2)
{
for(; j < n2; j++, k++)
{
arr[k] = R[j];
}
}
}
void mergesort(int* arr, int p, int r)
{
int q = 0;
if(p < r)
{
q = (p + r) / 2;
mergesort(arr, p, q);
mergesort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
int main()
{
int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
mergesort(a, 0, 7);
for(int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
非遞歸代碼實現(xiàn)：
/**
* merge_sort: 非遞歸實現(xiàn) --迭代
* 非遞歸思想: 將數(shù)組中的相鄰元素兩兩配對。用merge函數(shù)將他們排序，
* 構(gòu)成n/2組長度為2的排序好的子數(shù)組段，然后再將他們排序成長度為4的子數(shù)組段，
* 如此繼續(xù)下去，直至整個數(shù)組排好序。
**/ #include <stdio.h>
#include <stdlib.h>
// merge_sort(): 非遞歸實現(xiàn)-自底向上
// 將原數(shù)組劃分為left[min
max] 和 right[minmax]兩部分
void merge_sort(
int *list,
int length)
{
int i, left_min, left_max, right_min, right_max, next;
int *tmp = (
int*)malloc(
sizeof(
int) * length);
if (tmp == NULL)
{
fputs("Error: out of memory\n", stderr);
abort();
}
for (i = 1; i < length; i *= 2)
// i為步長，1,2,4,8……
{
for (left_min = 0; left_min < length - i; left_min = right_max)
{
right_min = left_max = left_min + i;
//right_min取left_max的值，以下要用到left_max的值才不會改變left_max原先值
right_max = left_max + i;
if (right_max > length)
//如果right_max超出了數(shù)組長度，則right_max等于數(shù)組長度
right_max = length;
next = 0;
while (left_min < left_max && right_min < right_max)
//tmp[next]存儲子數(shù)組中的最小值
tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];
while (left_min < left_max)
//如果left_min小于left_max，則將最小值原封不動地賦給list[--right_min]，right_min 要先減1
list[--right_min] = list[--left_max];
while (next > 0)
//將tmp[next]存儲的最小值放入list[--right_min]中
list[--right_min] = tmp[--next];
}
if(i == 1)
//打印第一次歸并后的數(shù)字排列
{
for(
int j=0;j<length;j++)
printf("%d ",list[j]);
printf("\n");
}
}
free(tmp);
}
int main()
{
int a[1000],t,i;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
merge_sort(a, t);
// print array
for (i = 0; i < t; i++)
printf("%d ", a[i]);
return 0;
}