C說話歸並排序及實例代碼。本站提示廣大學習愛好者：（C說話歸並排序及實例代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話歸並排序及實例代碼正文
合並排序也稱歸並排序，其算法思惟是將待排序序列分為兩部門，順次對分得的兩個部門再次應用合並排序，以後再對其停止歸並。僅從算法思惟上懂得合並排序會認為很籠統，接上去就以對序列A[0], A[l]…, A[n-1]停止升序分列來停止講授，在此采取自頂向下的完成辦法。
操作步調以下：
(1)將所要停止的排序序列分為閣下兩個部門，假如要停止排序的序列的肇端元素下標為first，最初一個元素的下標為last，那末閣下兩部門之間的臨界點下標mid=(first+last)/2，這兩部門分離是A[first … mid]和A[mid+1 … last]。
(2)將下面所分得的兩部門序列持續依照步調(1)持續停止劃分，直到劃分的區間長度為1。
(3)將劃分停止後的序列停止合並排序，排序辦法為對所分的n個子序列停止兩兩歸並，獲得n/2或n/2+l個含有兩個元素的子序列，再對獲得的子序列停止歸並，直至獲得一個長度為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));
//請求空間，使其年夜小為兩個
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;
}
運轉成果：
排序前
32 12 56 78 76 45 36
排序後
12 32 36 45 56 76 78
剖析下面的運轉成果，經由過程合並排序勝利地完成了對給定序列的排序操作。接上去經由過程圖來懂得合並排序的詳細操作流程。
鄙人圖先對所要停止排序的序列停止分化，直到分為單個元素為止，然後將其停止兩兩歸並。因為終究分化成單個元素，是以在歸並的時刻.將小數放在後面，年夜數放在前面，獲得一個有序序列。接上去對兩個相連的有序序列停止排序，先比擬有序序列中的第一個元素，將較小的元素放入暫時數組中，接著將較小元素地點數組的下一個元素與另外一個數組中的較小元素比擬，異樣將較小元素放入暫時數組中，順次停止，直到兩個數組的一切元素都放入暫時數組中，最初再將暫時數組的元素放入原始數組中的對應地位。
以上就是對歸並排序的具體講授，願望對你有贊助。
