一、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（divide and conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并過(guò)程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。
二、歸并操作
三、兩路歸并算法
1、算法基本思路
設(shè)兩個(gè)有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：r[low..m]，r[m+1..high]，先將它們合并到一個(gè)局部的暫存向量r1(相當(dāng)于輸出堆)中，待合并完成后將r1復(fù)制回r[low..high]中。
（1）合并過(guò)程
合并過(guò)程中，設(shè)置i，j和p三個(gè)指針，其初值分別指向這三個(gè)記錄區(qū)的起始位置。合并時(shí)依次比較r[i]和r[j]的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到r1[p]中，然后將被復(fù)制記錄的指針i或j加1，以及指向復(fù)制位置的指針p加1。
重復(fù)這一過(guò)程直至兩個(gè)輸入的子文件有一個(gè)已全部復(fù)制完畢(不妨稱其為空)，此時(shí)將另一非空的子文件中剩余記錄依次復(fù)制到r1中即可。
（2）動(dòng)態(tài)申請(qǐng)r1
實(shí)現(xiàn)時(shí)，r1是動(dòng)態(tài)申請(qǐng)的，因?yàn)樯暾?qǐng)的空間可能很大，故須加入申請(qǐng)空間是否成功的處理。
2、歸并算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void merge(seqlist r，int low，int m，int high) {//將兩個(gè)有序的子文件r[low..m)和r[m+1..high]歸并成一個(gè)有序的 //子文件r[low..high] int i=low，j=m+1，p=0； //置初始值 rectype *r1； //r1是局部向量，若p定義為此類型指針?biāo)俣雀? r1=(reetype *)malloc((high-low+1)*sizeof(rectype))； if(! r1) //申請(qǐng)空間失敗 error("insufficient memory available!")； while(i<=m&&j<=high) //兩子文件非空時(shí)取其小者輸出到r1[p]上 r1[p++]=(r[i].key<=r[j].key)?r[i++]：r[j++]； while(i<=m) //若第1個(gè)子文件非空，則復(fù)制剩余記錄到r1中 r1[p++]=r[i++]； while(j<=high) //若第2個(gè)子文件非空，則復(fù)制剩余記錄到r1中 r1[p++]=r[j++]； for(p=0，i=low；i<=high；p++，i++) r[i]=r1[p]；//歸并完成后將結(jié)果復(fù)制回r[low..high] } //merge |
四、歸并排序
歸并排序有兩種實(shí)現(xiàn)方法：自底向上和自頂向下。下面說(shuō)說(shuō)自頂向下的方法
（1）分治法的三個(gè)步驟
設(shè)歸并排序的當(dāng)前區(qū)間是r[low..high]，分治法的三個(gè)步驟是：
①分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)
②求解：遞歸地對(duì)兩個(gè)子區(qū)間r[low..mid]和r[mid+1..high]進(jìn)行歸并排序；
③組合：將已排序的兩個(gè)子區(qū)間r[low..mid]和r[mid+1..high]歸并為一個(gè)有序的區(qū)間r[low..high]。
遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1（一個(gè)記錄自然有序）。
（2）具體算法
|
1
2
3
4
5
6
7
8
9
10
|
void mergesortdc(seqlist r，int low，int high) {//用分治法對(duì)r[low..high]進(jìn)行二路歸并排序 int mid； if(low<high){//區(qū)間長(zhǎng)度大于1 mid=(low+high)/2； //分解 mergesortdc(r，low，mid); //遞歸地對(duì)r[low..mid]排序 mergesortdc(r，mid+1，high)； //遞歸地對(duì)r[mid+1..high]排序 merge(r，low，mid，high)； //組合，將兩個(gè)有序區(qū)歸并為一個(gè)有序區(qū) } }//mergesortdc |
（3）算法mergesortdc的執(zhí)行過(guò)程
算法mergesortdc的執(zhí)行過(guò)程如下圖所示的遞歸樹(shù)。
五、算法分析
1、穩(wěn)定性
歸并排序是一種穩(wěn)定的排序。
2、存儲(chǔ)結(jié)構(gòu)要求
可用順序存儲(chǔ)結(jié)構(gòu)。也易于在鏈表上實(shí)現(xiàn)。
3、時(shí)間復(fù)雜度
對(duì)長(zhǎng)度為n的文件，需進(jìn)行 趟二路歸并，每趟歸并的時(shí)間為o(n)，故其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是o(nlgn)。
4、空間復(fù)雜度
需要一個(gè)輔助向量來(lái)暫存兩有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為o(n)，顯然它不是就地排序。
注意：
若用單鏈表做存儲(chǔ)結(jié)構(gòu)，很容易給出就地的歸并排序。
5、比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。
6、賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)
7、歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。
六、代碼實(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
75
76
77
78
79
80
81
|
public class mergesorttest { public static void main(string[] args) { int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 }; system.out.print("初始化：\t"); print(data); system.out.println(""); mergesort(data, 0, data.length - 1); system.out.print("\n排序后: \t"); print(data); } public static void mergesort(int[] data, int left, int right) { if (left >= right) return; //兩路歸并 // 找出中間索引 int center = (left + right) / 2; // 對(duì)左邊數(shù)組進(jìn)行遞歸 mergesort(data, left, center); // 對(duì)右邊數(shù)組進(jìn)行遞歸 mergesort(data, center + 1, right); // 合并 merge(data, left, center, center + 1, right); system.out.print("排序中:\t"); print(data); } /** * 將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面2個(gè)數(shù)組已有序，歸并后依然有序 * * @param data * 數(shù)組對(duì)象 * @param leftstart * 左數(shù)組的第一個(gè)元素的索引 * @param leftend * 左數(shù)組的最后一個(gè)元素的索引 * @param rightstart * 右數(shù)組第一個(gè)元素的索引 * @param rightend * 右數(shù)組最后一個(gè)元素的索引 */ public static void merge(int[] data, int leftstart, int leftend, int rightstart, int rightend) { int i = leftstart; int j = rightstart; int k = 0; // 臨時(shí)數(shù)組 int[] temp = new int[rightend - leftstart + 1]; //創(chuàng)建一個(gè)臨時(shí)的數(shù)組來(lái)存放臨時(shí)排序的數(shù)組 // 確認(rèn)分割后的兩段數(shù)組是否都取到了最后一個(gè)元素 while (i <= leftend && j <= rightend) { // 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組 if (data[i] > data[j]) { temp[k++] = data[j++]; } else { temp[k++] = data[i++]; } } // 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while只會(huì)執(zhí)行其中一個(gè)） while (i <= leftend) { temp[k++] = data[i++]; } while (j <= rightend) { temp[k++] = data[j++]; } k = leftstart; // 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中 // （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組） for (int element : temp) { data[k++] = element; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { system.out.print(data[i] + "\t"); } system.out.println(); } } |
七、運(yùn)行結(jié)果
|
1
2
3
4
5
6
7
8
9
10
11
|
初始化： 2 4 7 5 8 1 3 6 排序中: 2 4 7 5 8 1 3 6排序中: 2 4 5 7 8 1 3 6排序中: 2 4 5 7 8 1 3 6排序中: 2 4 5 7 1 8 3 6排序中: 2 4 5 7 1 8 3 6排序中: 2 4 5 7 1 3 6 8排序中: 1 2 3 4 5 6 7 8 排序后: 1 2 3 4 5 6 7 8 |
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/ouyang_peng/article/details/46625155
