分治法最常用的就是將規模為n的實例劃分成兩個n規模為n/2的實例 。推廣到一般的情況，我們可以將規模為n的實例劃分為b個規模為n/b的實例。這樣對于算法的運行時間存在遞推式：T(n) = aT（n/b）+f（n），這個式子又被稱為通用分治遞推式。

我們假定遞推式中的f(n)∈O(n^d)，其中d>=0，那么：

所以，對于等分的T(n) = 2T(n/2) + 1,因為a=2,b=2,d=0,并且a > b^d

則T(n) = O(n);

上面這個式子就是用來求解遞推式結果的。

?

歸并排序：（時間復雜度O(nlogn)）

對于一個需要排序的數組a[0 - n-1]，先將數組一分為二a[0 - n/2-1]和a[n/2+1 - n]，對子數組排序，之后合并為一個有序數組

?

import java.util.Arrays;public class Main {// 合并兩個有序數組public static void merge(int[] a, int low, int mid, int high) {int[] temp = new int[high - low + 1];int i = low;// 左指針int j = mid + 1;// 右指針int k = 0;// 把較小的數先移到新數組中while (i <= mid && j <= high) {if (a[i] < a[j]) {temp[k++] = a[i++];} else {temp[k++] = a[j++];}}while (i <= mid) {temp[k++] = a[i++];}while (j <= high) {temp[k++] = a[j++];}// 把新數組中的數覆蓋a數組for (int k2 = 0; k2 < temp.length; k2++) {a[k2 + low] = temp[k2];}}// 遞歸分解數組，當待排序的序列長度為1時，判定為有序public static void mergeSort(int[] a, int low, int high) {int mid = (low + high) / 2;if (low < high) {// 左邊mergeSort(a, low, mid);// 右邊mergeSort(a, mid + 1, high);// 左右歸并merge(a, low, mid, high);System.out.println(Arrays.toString(a));}}public static void main(String[] args) {int[] a = {8, 3, 2, 9, 7, 1, 5, 4};mergeSort(a, 0, a.length - 1);System.out.println("排序結果：" + Arrays.toString(a));} }

歸并排序在最壞情況下的鍵值比較次數十分接近基于比較的排序算法在理論上能夠達到的最少次數。

此外快速排序和堆排序的時間復雜度也是O(nlogn)，但是相比來說，歸并排序在于其穩定性

總結

以上是生活随笔為你收集整理的分治法在排序算法中的应用（JAVA）--归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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