本文實(shí)例講述了java數(shù)據(jù)結(jié)構(gòu)排序算法之歸并排序。分享給大家供大家參考，具體如下：
在前面說的那幾種排序都是將一組記錄按關(guān)鍵字大小排成一個(gè)有序的序列，而歸并排序的思想是：基于合并，將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表
歸并排序算法：假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1,然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2（n為奇數(shù)的時(shí)候，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列。在此基礎(chǔ)上，再對(duì)長(zhǎng)度為2的有序子序列進(jìn)行亮亮歸并，得到若干個(gè)長(zhǎng)度為4的有序子序列。如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法被稱作是：2-路歸并排序（基本操作是將待排序列中相鄰的兩個(gè)有序子序列合并成一個(gè)有序序列）。
算法實(shí)現(xiàn)代碼如下：
|
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
package exp_sort;public class MergeSort { /** * 相鄰兩個(gè)有序子序列的合并算法 * * @param src_array * @param low * @param high * @param des_array */ public static void Merge(int src_array[], int low, int high, int des_array[]) { int mid; int i, j, k; mid = (low + high) / 2; i = low; k = 0; j = mid + 1; // compare two list while (i <= mid && j <= high) { if (src_array[i] <= src_array[j]) { des_array[k] = src_array[i]; i = i + 1; } else { des_array[k] = src_array[j]; j = j + 1; } k = k + 1; } // if 1 have,cat while (i <= mid) { des_array[k] = src_array[i]; k = k + 1; i = i + 1; } while (j <= high) { des_array[k] = src_array[j]; k = k + 1; j = j + 1; } for (i = 0; i < k; i++) { src_array[low + i] = des_array[i]; } } /** * 2-路歸并排序算法，遞歸實(shí)現(xiàn) * * @param src_array * @param low * @param high * @param des_array */ public static void mergeSort(int src_array[], int low, int high, int des_array[]) { int mid; if (low < high) { mid = (low + high) / 2; mergeSort(src_array, low, mid, des_array); mergeSort(src_array, mid + 1, high, des_array); Merge(src_array, low, high, des_array); } } public static void main(String[] args) { // TODO Auto-generated method stub int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; int array2[] = new int[array1.length]; mergeSort(array1, 0, array1.length - 1, array2); System.out.println("\n----------after sort-------------"); for (int ii = 0; ii < array1.length; ii++) { System.out.print(array1[ii] + " "); } System.out.println("\n"); }} |
代碼解釋：
歸并排序中一趟歸并要多次調(diào)用到2-路歸并算法，一趟的歸并的時(shí)間復(fù)雜度是O(n)，合并兩個(gè)已經(jīng)排好序的表的時(shí)間顯然是線性的，因?yàn)樽疃噙M(jìn)行了n-1次比較，其中n是元素的總數(shù)。如果有多個(gè)數(shù)，即n不為1時(shí)，遞歸的將前半部分?jǐn)?shù)據(jù)和后半部分?jǐn)?shù)據(jù)各自歸并排序，得到排序后的兩部分?jǐn)?shù)據(jù)，再合并到一起。
算法分析：
該算法是建立在歸并操作（也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作）上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，它將問題分成一些小的問題然后遞歸求解，而治的階段則是將分的階段解得的各個(gè)答案修補(bǔ)到一塊；分治是遞歸非常有力的用法。注意：與快速·排序和堆排序比較，歸并排序最大的特點(diǎn)就是，它一種穩(wěn)定的排序方法。速度僅次于快速排序，一般用于對(duì)總體無序，但是各子項(xiàng)相對(duì)有序的數(shù)列。
復(fù)雜度：
時(shí)間復(fù)雜度為：O(nlogn) ——該算法最好、最壞和平均的時(shí)間性能。
空間復(fù)雜度為 ：O(n)
比較操作的次數(shù)介于(nlogn) / 2和 nlogn - n + 1之間。
賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)
很難用于主存排序（歸并排序比較占用內(nèi)存，主要問題在于合并兩個(gè)排序的表需要線性附加內(nèi)存，在整個(gè)算法中還要花費(fèi)將數(shù)據(jù)拷貝到臨時(shí)數(shù)組再拷貝回來這樣的一些附加操作，其結(jié)果嚴(yán)重放慢了排序的速度）但是效率很高，主要用于外部排序，對(duì)于重要的內(nèi)部排序應(yīng)用而言，一般還是選擇快速排序。
歸并操作的步驟如下：
第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針達(dá)到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
歸并排序的步驟如下（假設(shè)序列共有n個(gè)元素）：
將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素
將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素
重復(fù)步驟2，直到所有元素排序完畢
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
