歸并排序算法介紹

歸并排序（Merging Sort）就是利用歸并的思想實現排序的放。它的原理是假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并,.....，如此重復，直到得到一個長度為n的有序序列為止，這種排序方法稱為2路歸并排序。

歸并排序算法圖解

歸并排序算法代碼

其實歸并排序思路很好理解，就是將2個有序的序列合并，整個序列都是無序的哪里去找有序的序列？我們可以無限遞歸，將其劃分為1個元素的序列，這時肯定是有序的咯，然后一路歸并排序 就ok呀。主要是合并代碼，仔細看 是不是應該這樣去合并！

//歸并排序的合并數組函數 升序 void Merge_Up(int *arr, int start, int mid, int end, int *temp) {int i_start = start;int i_end = mid;int j_start = mid + 1;int j_end = end;int length = 0;while (i_start <= i_end && j_start <= j_end){//升序 我小先放我if (arr[i_start] < arr[j_start]){temp[length] = arr[i_start];length++;i_start++;}else{temp[length] = arr[j_start];length++;j_start++;}}//將剩余沒有放完的放置到輔助空間中去while (i_start <= i_end){temp[length] = arr[i_start];length++;i_start++;}while (j_start <= j_end){temp[length] = arr[j_start];length++;j_start++;}//將輔助空間的值復制到源數組for (int i = 0; i < length; i++){arr[start + i] = temp[i];}return; }/* 歸并排序@param arr 歸并排序的數組@param start 開始下標@param end 結束下標@param temp 輔助空間 */ void MergeSort_Up(int *arr,int start,int end,int* temp) {if (start >= end){return;}int mid = (start + end )/ 2;//分組//左半部分 進行歸并排序MergeSort_Up(arr, start, mid, temp);//右半部分 進行歸并排序MergeSort_Up(arr, mid + 1, end, temp);//合并排序好的2個數組Merge_Up(arr, start, mid, end, temp);}

完整代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h> #define MAXSIZE 1000000 //交換值 void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp; } //打印數組元素 void PrintArr(int* arr, int length) {for (int i = 0; i < length; i++){printf("%d ", arr[i]);}printf("\n");return; } long GetSysTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm; } //歸并排序的合并數組函數 降序 void Merge_Down(int *arr, int start, int mid, int end, int *temp) {int i_start = start;int i_end = mid;int j_start = mid + 1;int j_end = end;int length = 0;//只有 1個元素時肯定是有序的，做為遞歸函數的出口。if (start >= end){return;}while (i_start <= i_end && j_start <= j_end){//降序 我大先放我if (arr[i_start] > arr[j_start]){temp[length] = arr[i_start];length++;i_start++;}else{temp[length] = arr[j_start];length++;j_start++;}}//將輔助空間的值復制到源數組for (int i = 0; i < length; i++){arr[start + i] = temp[i];}} //歸并排序的合并數組函數 升序 void Merge_Up(int *arr, int start, int mid, int end, int *temp) {int i_start = start;int i_end = mid;int j_start = mid + 1;int j_end = end;int length = 0;while (i_start <= i_end && j_start <= j_end){//升序 我小先放我if (arr[i_start] < arr[j_start]){temp[length] = arr[i_start];length++;i_start++;}else{temp[length] = arr[j_start];length++;j_start++;}}//將剩余沒有放完的放置到輔助空間中去while (i_start <= i_end){temp[length] = arr[i_start];length++;i_start++;}while (j_start <= j_end){temp[length] = arr[j_start];length++;j_start++;}//將輔助空間的值復制到源數組for (int i = 0; i < length; i++){arr[start + i] = temp[i];}return; }/* 歸并排序@param arr 歸并排序的數組@param start 開始下標@param end 結束下標@param temp 輔助空間 */ void MergeSort_Up(int *arr,int start,int end,int* temp) {if (start >= end){return;}int mid = (start + end )/ 2;//分組//左半部分 進行歸并排序MergeSort_Up(arr, start, mid, temp);//右半部分 進行歸并排序MergeSort_Up(arr, mid + 1, end, temp);//合并排序好的2個數組Merge_Up(arr, start, mid, end, temp);}int main(int argc, char *argv[]) {srand((size_t)time(NULL));//設置隨機種子int arr[10] = { 6,8,2,3,9,7,4,1,5,10 };int *arr2 = (int*)malloc(sizeof(int)*MAXSIZE);//int *arr3 = (int*)malloc(sizeof(int)*MAXSIZE);//給每個元素設置一個隨機值for (int i = 0; i < MAXSIZE; i++){int num = rand() % MAXSIZE;arr2[i] = num;//arr3[i] = num;}int *temp = (int*)malloc(sizeof(int)*10);int *temp1 = (int*)malloc(sizeof(int) * MAXSIZE);printf("排序前：\n");PrintArr(arr, 10);MergeSort_Up(arr, 0, 9, temp);printf("歸并排序升序：\n");PrintArr(arr, 10);long start = GetSysTime();MergeSort_Up(arr2, 0, MAXSIZE - 1, temp1);long end = GetSysTime();printf("%d個元素 歸并排序耗費%d毫秒\n",MAXSIZE,end-start);return 0; }

代碼運行檢測

總結

以上是生活随笔為你收集整理的排序算法：归并排序算法实现及分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。