本文實例講述了Java分治歸并排序算法。分享給大家供大家參考，具體如下：
1、分治法
許多有用的算法在結構上是遞歸的：為了解決一個給定的問題，算法一次或多次遞歸地調用其自身以解決緊密相關的若干子問題。這些算法典型地遵循分治法的思想：將原問題分解為幾個規模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。
分治模式在每層遞歸時都有三個步驟：
（1）分解原問題為若干子問題，這些子問題是原問題的規模較小的實例。
（2）解決這些子問題，遞歸地求解各子問題。然而，若子問題的規模足夠小，則直接求解。
（3）合并這些子問題的解成原問題的解。
2、歸并排序算法
歸并排序算法完全遵循分治模式。直觀上其操作如下：
（1）分解：分解待排序的n個元素的序列成各具n/2個元素的兩個子序列。
（2）解決：使用歸并排序遞歸地排序兩個子序列。
（3）合并：合并兩個已排序的子序列以產生已排序的答案。
當待排序的序列長度為1時，遞歸“開始回升”，在這種情況下不要做任何工作，因為長度為1的每個序列都已排好序。歸并排序算法的關鍵操作是“合并”步驟中兩個已排序序列的合并。我們通過調用一個輔助過程Merge(A,p,q,r)來完成合并，其中A是一個數組，p、q和r是數組下標，滿足p<=q<r。該過程假設子數組A[p,q]和A[q+1,r]都已排好序。它合并這兩個子數組形成單一的已排好序的子數組并代替當前的子數組A[p,r]。
過程Merge按以下方式工作。回到我們玩撲克牌的例子，假設桌上有兩堆牌面朝上的牌，每堆都已排序，最小的牌在頂上。我們希望把這兩堆牌合并成單一的排好序的輸出堆，牌面朝下地放在桌上。我們的基本步驟包括在牌面朝上的兩堆牌的頂上兩張牌中選取較小的一張，將該牌從其堆中移開（該堆的頂上將顯露一張新牌）并牌面朝下地將該牌放置到輸出堆。
下面是Merge的偽代碼：
Merge(A,p,q,r)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
tmp[1,..,r-p+1]i = pj = q+1while i <= q && j <= r if A[i] <= A[j] tmp[k++] = A[i++]; else tmp[k++] = A[j++]; while i <= q tmp[k++] = A[i++]; while j <= r tmp[k++] = A[j++]; for k2 = 0 to tmp.length A[k2+p] = tmp[k2]; |
現在我們可以把過程Merge作為歸并排序算法中的一個子程序來用。下面的過程Merge_sort(A,p,r)排序子數組A[p,r]中的元素。若p>=r，則該子數組最多有一個元素，所以已經排好序。否則，分解步驟簡單地計算一個下標q，將A[p,r]分成兩個子數組A[p,q]和A[q+1,r]，前者包含[n/2]個元素，后者包含[n/2]個元素。
|
1
2
3
4
5
6
|
Merge_sort(A,p,r):if p < r q = (p+r)/2 Merge_sort(A,p,q) Merge_sort(A,q+1,r) Merge(A,p,q,r) |
為了排序整個序列A=(A[0],A[1],...,A[n])，我們執行初始調用Merge_sort(A,0,A.length)，這里再次有A.length = n。圖2-4自底向上地說明了當n為2的冪時該過程的操作。算法由以下操作組成：合并只含1項的序列對形成長度為2的排好序的序列，合并長度為2的序列對形成長度為4的排好序的序列，依此下去，直到長度為n/2的兩個序列被合并最終形成長度為n的排好序的序列。
3、Java代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
public class Merge_sort_test { public static void Merge(int[] A,int p,int q,int r){ int[] tmp = new int[r-p+1];//聲明一個臨時數組，長度為要歸并數組的長度 int i = p; //記住左邊數組第一個元素的下標 int j = q+1; //記住右邊數組第一個元素的下標 int k = 0; while(i <= q && j <= r){ //左邊數組元素和右邊數組元素比較，把小的元素賦給臨時數組 if(A[i] <= A[j]){ tmp[k++] = A[i++]; } else{ tmp[k++] = A[j++]; } } //把左邊剩余的數組元素賦給臨時數組 while(i <= q){ tmp[k++] = A[i++]; } //把右邊剩余的數組元素賦給臨時數組 while(j <= r){ tmp[k++] = A[j++]; } //用臨時數組元素覆蓋原數組元素 for(int k2 = 0;k2 < tmp.length;k2++){ A[k2+p] = tmp[k2]; } } public static void/*int[]*/ Merge_sort(int[] A,int p,int r){ int q = (p+r)/2; if(p < r){ //遞歸調用 Merge_sort(A,p,q); Merge_sort(A,q + 1,r); //歸并排序數據元素 Merge(A,p,q,r); } //return A; } public static void main(String[] args) { // int[] A = {5,2,4,7,1,3,2,6}; System.out.println("原始數據： "); for(int i = 0;i < A.length;i++){ System.out.print(A[i] + " "); } System.out.println(); Merge_sort(A,0,A.length -1); System.out.println("輸出結果： "); for(int i = 0;i < A.length;i++){ System.out.print(A[i] + " "); } }} |
希望本文所述對大家java程序設計有所幫助。
原文鏈接：http://blog.csdn.net/m53931422/article/details/41788535
