歸并排序
基本思想:
將兩個(gè)有序表合并成一個(gè)有序表。
歸并排序.gif
歸并排序示例:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 狀態(tài) |
|---|---|---|---|---|---|---|---|---|
| 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49' | 初始狀態(tài) |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | |
| 38 | 49 | 65 | 97 | 76 | 13 | 27 | 49' | |
| 38 | 49 | 65 | 97 | 13 | 76 | 27 | 49' | |
| 38 | 49 | 65 | 97 | 13 | 76 | 27 | 49' | |
| 38 | 49 | 65 | 97 | 13 | 27 | 49' | 76 | |
| 13 | 27 | 38 | 49' | 49 | 65 | 76 | 97 |
代碼：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] s = { 49, 38, 65, 97, 76, 13, 27, 49 };
new MergeSort().mergeSort(s, 0, s.length - 1);
for (int i = 0; i < s.length; i++) {
System.out.printf("%d ", s[i]);
}
}
void mergeSort(int s[], int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(s, start, mid);
mergeSort(s, mid + 1, end);
merge(s, start, mid, end);
}
}
void merge(int s[], int start, int mid, int end) {
int[] temp = new int[s.length];
int p1 = start, p2 = mid + 1, k = start;
while (p1 <= mid && p2 <= end) {
if (s[p1] <= s[p2]) {
temp[k++] = s[p1++];
} else {
temp[k++] = s[p2++];
}
}
while (p1 <= mid) {
temp[k++] = s[p1++];
}
while (p2 <= end) {
temp[k++] = s[p2++];
}
for (int i = start; i <= end; i++) {
s[i] = temp[i];
}
}
輸出：
13 27 38 49 49 65 76 97
歸并排序的效率分析
| 排序算法 | 平均時(shí)間性能 | 最好時(shí)間性能 | 最壞時(shí)間性能 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 歸并排序 |  |
|
|
 |
穩(wěn)定 |
- 歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)雜度的乘積胀糜。對(duì) n個(gè)元素的表，將這n個(gè)元素看作葉結(jié)點(diǎn)瓜富，若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn)写妥，則歸并過(guò)程對(duì)應(yīng)由葉向根生成一棵二叉樹(shù)的過(guò)程。所以歸并趟數(shù)等于二叉數(shù)的高度減1舀瓢，即?log2n?黔衡。每一趟歸并需移動(dòng) n個(gè)元素蚓聘，即每一趟歸并的時(shí)間復(fù)雜度為O(n)。因此盟劫，2-路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)夜牡。
- 利用歸并排序時(shí)，需要利用與待排序數(shù)組相同的輔助數(shù)組作臨時(shí)單元捞高，故該排序方法的空間復(fù)雜度為O(n)氯材，比前面介紹的其它排序方法占用的空間大。
- 由于歸并排序中硝岗，每?jī)蓚€(gè)有序表合并成一個(gè)有序表時(shí)氢哮，若分別在兩個(gè)有序表中出現(xiàn)有相同排序碼，則會(huì)使前一個(gè)有序表中相同排序碼先復(fù)制型檀，后一有序表中相同排序碼后復(fù)制冗尤，從而保持它們的相對(duì)次序不會(huì)改變。所以，歸并排序是一種穩(wěn)定的排序方法裂七。
