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("%dt",a[i]);
merge_sort(a,0,N-1); // 排序
printf ("n 排序後 n");
for(i=0;i<N;i++)
printf("%dt",a[i]); printf("n");
system("pause");
return 0;
}
運行結果:
排序前
32 12 56 78 76 45 36
排序後
12 32 36 45 56 76 78
分析上面的運行結果,通過歸併排序成功地實現了對給定序列的排序操作。接下來通過圖來了解歸併排序的具體操作流程。
在下圖先對所要進行排序的序列進行分解,直到分為單個元素為止,然後將其進行兩兩合併。由於最終分解成單個元素,因此在合併的.時候.將小數放在前面,大數放在後面,得到一個有序序列。接下來對兩個相連的有序序列進行排序,先比較有序序列中的第一個元素,將較小的元素放入臨時數組中,接着將較小元素所在數組的下一個元素與另一個數組中的較小元素比較,同樣將較小元素放入臨時數組中,依次進行,直到兩個數組的所有元素都放入臨時數組中,最後再將臨時數組的元素放入原始數組中的對應位置。
-
2017年3月計算機二級C語言考試摸底測試題
以下是yjbys考試網小編整理的2017年3月計算機二級C語言考試摸底測試題,希望對大家有所幫助,祝大家計算機二級考試順利通過。一、選擇題(每小題1分。)(1)程序流程圖中帶有箭頭的線段表示的是()。A.圖元關係B.數據流C.控制流D.調用關係(2)結構化程序設計的基本原則...
-
C語言if else語句彙總
對於很多情況,順序結構的代碼是遠遠不夠的,大家都接觸過C語言吧,下面是小編為大家整理的C語言ifelse語句,希望對大家有所幫助。C語言ifelse語句在C語言中,使用if和else關鍵字對條件進行判斷。請先看下面的代碼:#includeintmain(){intage;printf("請輸入你的年齡:");sc...
-
C語言精選面試題詳解
C語言是IT編程中最基礎的語言,在面試中,基本可以忽略又或者格外重要。下面是小編為大家整理的C語言精選面試題詳解,歡迎參考~分析這些面試題,本身包含很強的趣味性;而作為一名研發人員,通過對這些面試題的深入剖析則可進一步增強自身的內功。試題1:以下是引用片段:voi...
-
2017年計算機二級考試C語言備考題及答案
計算機二級對於很多考生來説還是比較有難度的,那麼怎樣順利通過二級考試呢?這就需要大家平時多練習和找方法了。以下是本站小編整理的2017年計算機二級考試C語言備考題及答案,希望對大家有幫助!1.(A)是構成C語言程序的基本單位。A、函數B、過程C、子程序D、子例...