基本思想: 歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有 序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
歸并排序核心步驟:先將數組分組,往下分直到分為1個數據,然后開始合并,兩兩合并,合并的時候先比較兩組數據中的數據的大小,按順序依次合并到臨時數組temp中,然后再將合并到temp數組中有序的數據覆蓋到原數組中。
#include <stdio.h>
// 歸并排序
// 時間復雜度O(N*logN)
// 空間復雜度O(N)
void _MergeSort(int* arr, int left, int right, int* temp)
{if (left >= right)return;// 遞歸劃分區間,直到區間內只有一個數據后開始歸并int mid = (left + right) / 2;// [left,mid] [mid+1,right]_MergeSort(arr, left, mid, temp);_MergeSort(arr, mid+1, right, temp);// 歸并[left,mid] [mid+1,right]有序,歸并到temp了int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段沒結束,具體那一段不知道,只有一個循環可以進入while(begin1<=end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 將歸并后在temp的數據拷貝回原數組for (int i = left;i <= right; i++){arr[i] = temp[i];}
}// 歸并排序
void MergeSort(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);// 傳入閉區間【0,n-1】_MergeSort(arr, 0, n - 1, temp);free(temp);
}void TestMergeSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}void TestMergeSortNonR()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSortNonR(arr,sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{//TestInsertSort();//TestShellSort();//TestSelectSort();//TestBubbleSort();//TestHeapSort();//TestQuickSort();TestMergeSort();TestMergeSortNonR();return 0;
}
函數的遞歸實現圖:
非遞歸法
從上面的遞歸圖可以看出,合并的時候是2個數據開始合并,也就是區間【0,0】和【1,1】合并,【2,2】和【3,3】合并;然后【0,1】和【2,3】合并到這里時是兩個數據兩個數據之間合并,依次類推。那么非遞歸方法,需要控制好合并的下標即可。
// 歸并排序--非遞歸方法
void MergeArry(int* arr, int begin1, int end1, int begin2, int end2, int* temp)
{int left = begin1, right = end2;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段沒結束,具體那一段不知道while (begin1 <= end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 將歸并后在temp的數據拷貝回原數組for (int i = left;i <= right; i++){arr[i] = temp[i];}
}void MergeSortNonR(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);int gap = 1; // 控制幾個數據的合并排序while (gap < n){for (int i = 0;i < n;i += 2 * gap){// 歸并+排序的區間(數組長度不是2的次方數時第二組可能會越界訪問)// [i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1; // 第一組int begin2 = i + gap, end2 = i + 2 * gap - 1; // 第二組// 1、合并時只有第一組if (begin2 >= n)break;// 2、合并時第二組只有部分數據,需要修正邊界if (end2 >= n)end2 = n - 1; // 只有一個數值的時候,直接讓end2=最后一個數值就行了MergeArry(arr, begin1, end1, begin2, end2, temp);}Printarry(arr, n);gap *= 2;}free(temp);
}
實現圖:
結論:
歸并排序是一種基于分治思想的有效排序算法,其核心是通過遞歸將數組不斷二分直至單個元素,然后按順序合并有序子序列。算法分為遞歸和非遞歸兩種實現方式:遞歸法通過_MergeSort函數劃分區間并調用自身,然后將有序子序列合并到臨時數組后回寫;非遞歸法使用MergeSortNonR函數,通過gap變量控制合并步長,逐步擴大有序區間。兩種方法都使用MergeArry函數進行具體合并操作,時間復雜度均為O(N*logN),空間復雜度為O(N)。代碼示例展示了完整的實現過程,包括邊界處理和數據拷貝等關鍵步驟。