1. 基本定義
歸并排序 (merge sort) 是一類(lèi)與插入排序、交換排序狈定、選擇排序不同的另一種排序方法颂龙。歸并的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序有多路歸并排序纽什、兩路歸并排序 , 可用于內(nèi)排序措嵌，也可以用于外排序。這里僅對(duì)內(nèi)排序的兩路歸并方法進(jìn)行討論芦缰。
特點(diǎn)： 內(nèi)存占用高企巢，但是穩(wěn)定。
充分利用二分法的思想让蕾，利用了完全二叉樹(shù) 深度是log2n + 1的特性浪规，因此效率比較高基本原理: 對(duì)于給定的一組記錄或听，利用遞歸與分治算法將數(shù)據(jù)序列劃分成為越來(lái)越小的半子表，在對(duì)半子表排序笋婿， 最后再用遞歸方法將排好序的半子表合并成為越來(lái)越大的有序序列誉裆。
過(guò)程：先拆分 再聚合
時(shí)間復(fù)雜度： O(nlog2n)
-
空間復(fù)雜度： O(n)
image.png
- 代碼實(shí)現(xiàn)
public static void main(String[] args) {
int a[] = { 12, 14, 15, 13, 11, 16 };
mergeSort(a, 0, a.length - 1);
System.out.println("排序結(jié)果：" + Arrays.toString(a));
}
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 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;
// 把較小的數(shù)先移到新數(shù)組中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右邊邊剩余的數(shù)移入數(shù)組
while (j <= high) {
temp[k++] = a[j++];
}
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}
參考這篇文章，寫(xiě)的很好
https://www.cnblogs.com/chengxiao/p/6194356.html
