快捷導(dǎo)航

C語(yǔ)言合并排序及實(shí)例代碼

更新時(shí)間：2016年07月18日 16:17:08 投稿：lqh

本篇文章主要介紹C語(yǔ)言合并排序算法,這里對(duì)合并排序通過(guò)實(shí)例代碼進(jìn)行了詳細(xì)講解,希望能幫助到大家學(xué)習(xí)

歸并排序也稱(chēng)合并排序，其算法思想是將待排序序列分為兩部分，依次對(duì)分得的兩個(gè)部分再次使用歸并排序，之后再對(duì)其進(jìn)行合并。僅從算法思想上了解歸并排序會(huì)覺(jué)得很抽象，接下來(lái)就以對(duì)序列A[0], A[l]…, A[n-1]進(jìn)行升序排列來(lái)進(jìn)行講解，在此采用自頂向下的實(shí)現(xiàn)方法。

操作步驟如下：

(1)將所要進(jìn)行的排序序列分為左右兩個(gè)部分，如果要進(jìn)行排序的序列的起始元素下標(biāo)為first，最后一個(gè)元素的下標(biāo)為last，那么左右兩部分之間的臨界點(diǎn)下標(biāo)mid=(first+last)/2，這兩部分分別是A[first … mid]和A[mid+1 … last]。

(2)將上面所分得的兩部分序列繼續(xù)按照步驟(1)繼續(xù)進(jìn)行劃分，直到劃分的區(qū)間長(zhǎng)度為1。

(3)將劃分結(jié)束后的序列進(jìn)行歸并排序，排序方法為對(duì)所分的n個(gè)子序列進(jìn)行兩兩合并，得到n/2或n/2+l個(gè)含有兩個(gè)元素的子序列，再對(duì)得到的子序列進(jìn)行合并，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。

下面通過(guò)一段代碼來(lái)看如何實(shí)現(xiàn)歸并排序。

#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high){
 int i, k;
 int *tmp = (int *)malloc((high-low+1)*sizeof(int));
 //申請(qǐng)空間，使其大小為兩個(gè)
 int left_low = low;
 int left_high = mid;
 int right_low = mid + 1;
 int right_high = high;
 for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比較兩個(gè)指針?biāo)赶虻脑?
  if(arr[left_low]<=arr[right_low]){
   tmp[k] = arr[left_low++];
  }else{
   tmp[k] = arr[right_low++];
  }
 }
 if(left_low <= left_high){ //若第一個(gè)序列有剩余，直接復(fù)制出來(lái)粘到合并序列尾
 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
 for(i=left_low;i<=left_high;i++)
  tmp[k++] = arr[i];
 }
 if(right_low <= right_high){
 //若第二個(gè)序列有剩余，直接復(fù)制出來(lái)粘到合并序列尾
 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
  for(i=right_low; i<=right_high; i++)
   tmp[k++] = arr[i];
 }
 for(i=0; i<high-low+1; i++)
  arr[low+i] = tmp[i];
 free(tmp);
 return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
 int mid = 0;
 if(first<last){
  mid = (first+last)/2; /* 注意防止溢出 */
  /*mid = first/2 + last/2;*/
  //mid = (first & last) + ((first ^ last) >> 1);
  merge_sort(arr, first, mid);
  merge_sort(arr, mid+1,last);
  merge(arr,first,mid,last);
 }
 return;
}
int main(){
 int i;
 int a[N]={32,12,56,78,76,45,36};
 printf ("排序前 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]);
 merge_sort(a,0,N-1); // 排序
 printf ("\n 排序后 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]); printf("\n");
 system("pause");
 return 0;
}

運(yùn)行結(jié)果：

排序前

32 12 56 78 76 45 36

排序后

12 32 36 45 56 76 78

分析上面的運(yùn)行結(jié)果，通過(guò)歸并排序成功地實(shí)現(xiàn)了對(duì)給定序列的排序操作。接下來(lái)通過(guò)圖來(lái)了解歸并排序的具體操作流程。

在下圖先對(duì)所要進(jìn)行排序的序列進(jìn)行分解，直到分為單個(gè)元素為止，然后將其進(jìn)行兩兩合并。由于最終分解成單個(gè)元素，因此在合并的時(shí)候.將小數(shù)放在前面，大數(shù)放在后面，得到一個(gè)有序序列。接下來(lái)對(duì)兩個(gè)相連的有序序列進(jìn)行排序，先比較有序序列中的第一個(gè)元素，將較小的元素放入臨時(shí)數(shù)組中，接著將較小元素所在數(shù)組的下一個(gè)元素與另一個(gè)數(shù)組中的較小元素比較，同樣將較小元素放入臨時(shí)數(shù)組中，依次進(jìn)行，直到兩個(gè)數(shù)組的所有元素都放入臨時(shí)數(shù)組中，最后再將臨時(shí)數(shù)組的元素放入原始數(shù)組中的對(duì)應(yīng)位置。