C言語合并排序（兼并排序）算法及代碼

合并排序也稱兼并排序，其算法思惟是將待排序序列分為兩局部，順次對分得的兩個局部再次運用合并排序，之后再對其停止兼并。僅從算法思惟上理解合并排序會認為很籠統(tǒng)，接下來就以對序列A[0], A[l]…, A[n-1]停止升序陳列來停止解說，在此采取自頂向下的完成辦法，操作步調(diào)如下。
(1)將所要停止的排序序列分為閣下兩個局部，假如要停止排序的序列的肇端元素下標為first，最初一個元素的下標為last，那么閣下兩局部之間的臨界點下標mid=(first+last)/2，這兩局部辨別是A[first … mid]和A[mid+1 … last]。
(2)將下面所分得的兩局部序列持續(xù)依照步調(diào)(1)持續(xù)停止劃分，直到劃分的區(qū)間長度為1。
(3)將劃分完畢后的序列停止合并排序，排序辦法為對所分的n個子序列停止兩兩兼并，失掉n/2或n/2+l個含有兩個元素的子序列，再對失掉的子序列停止兼并，直至失掉一個長度為n的有序序列為止。下面經(jīng)過一段代碼來看若何完成合并排序。

			#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)); //請求空間，使其巨細為兩個 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++){ // 比擬兩個指針所指向的元素 if(arr[left_low]<=arr[right_low]){ tmp[k] = arr[left_low++]; }else{ tmp[k] = arr[right_low++]; } } if(left_low <= left_high){ //若第一個序列有殘剩，直接復制出來粘到兼并序列尾 //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){ //若第二個序列有殘剩，直接復制出來粘到兼并序列尾 //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; }

運轉(zhuǎn)后果：

排序前
32    12    56    78    76    45    36
排序后
12    32    36    45    56    76    78

剖析下面的運轉(zhuǎn)后果，經(jīng)過合并排序勝利地完成了對給定序列的排序操作。接下來經(jīng)過圖11-9來理解合并排序的詳細操作流程。
在圖11-9中，先對所要停止排序的序列停止分化，直到分為單個元素為止，然后將其停止兩兩兼并。因為最終分化成單個元素，因而在兼并的時分.將小數(shù)放在后面，大數(shù)放在前面，失掉一個有序序列。接下來對兩個相連的有序序列停止排序，先比擬有序序列中的第一個元素，將較小的元素放入暫時數(shù)組中，接著將較小元素地點數(shù)組的下一個元素與另一個數(shù)組中的較小元素比擬，異樣將較小元素放入暫時數(shù)組中，順次停止，直到兩個數(shù)組的一切元素都放入暫時數(shù)組中，最初再將暫時數(shù)組的元素放入原始數(shù)組中的對應地位。

圖11-9合并排序的操作流程