排序系列之(1)歸并排序及C語言實現
有很多算法在結構上是遞歸的:為了解決一個給定的問題,算法需要一次或多次遞歸的調用其本身來解決相關的問題。這些算法通常采用分治策略:將原問題劃分成n個規模較小而結構與原問題相似的子問題;遞歸的解決這些子問題,然后將結果合并,就能得到原問題的解。
分治模式在遞歸時一般都有三個步驟
分解:將原問題分解成一系類子問題
解決:遞歸的解各子問題。若子問題足夠小,則直接求解。
合并:將子問題的結果合并成原問題的解。
歸并排序在算法上完全依照了上述模式,操作如下。
分解:將n個元素分解成n/2個元素的子序列
解決:用合并排序法對兩個子序列遞歸地排序
合并:將子問題的結果合并原問題的解。
以下是源代碼實現
view plaincopy to clipboardprint?
void mergeSort(int a[],int left,int right)
{
int i;
// 保證至少有兩個元素
if(left < right)
{
i = (left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,left,right);
}
}
void merge(int a[],int left,int right)
{
int begin1 = left;
int mid = (left+right)/2 ;
int begin2 = mid+1;
int k=0;
int newArrayLen = right-left+1;
int *b = (int*)malloc(newArrayLen*sizeof(int));
while(begin1<=mid && begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
while(begin1<=mid)
b[k++] = a[begin1++];
while(begin2<=right)
b[k++] = a[begin2++];
copyArray(b,a,newArrayLen,left);
free(b);
}
/**
* 復制數組
* source:源數組
* dest:目標數組
* len:源數組長度
* first:目標數組起始位置
*
*/
void copyArray(int source[], int dest[],int len,int first)
{
int i;
int j=first;
for(i=0;i
{
dest[j] = source[i];
j++;
}
}
void mergeSortTest()
{
int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
int len = sizeof(a)/sizeof(int);
showArray(a,len);
mergeSort(a,0,len-1);
showArray(a,len);
}