基本思想

建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

算法原理

?歸并操作指的是將兩個已經排序的序列合并成一個序列的操作，歸并操作步驟如下：

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針到達序列尾
將另一序列剩下的所有元素直接復制到合并序列尾

特點

?數據結構：數組

?穩定性：穩定

過程

??????????

????排序過程????????????宏觀過程

復雜度與輔助空間

?最差時間復雜度：O(nlogn)

?最優時間復雜度：O(nlogn)

?平均時間復雜度：O(nlogn)

?所需輔助空間：O(n)

源程序

//將有二個有序數列a[first...mid]和a[mid...last]合并。 void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左邊有序 mergesort(a, mid + 1, last, temp); //右邊有序 mergearray(a, first, mid, last, temp); //再將二個有序數列合并 } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; }

?

總結

以上是生活随笔為你收集整理的归并排序(Merge_Sort)的全部內容，希望文章能夠幫你解決所遇到的問題。

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