歸并排序（Merging Sort）利用歸并的思想實(shí)現(xiàn)的排序方法擎淤。它的原理是假設(shè)初始序列含有n個(gè)記錄雁乡，則可以看成是n個(gè)有序的子序列，每個(gè)子序列長度為1盒延，然后兩兩歸并，得到[n/2]個(gè)長度為2或1的有序子序列然后反復(fù)進(jìn)行兩兩歸并鼠冕，直到得到一個(gè)長度為n的有序序列為止添寺。
時(shí)間復(fù)雜度
最好情況o(nlogn)
最壞情況o(nlogn)
排序穩(wěn)定，但需要額外的輔助空間
1.遞歸實(shí)現(xiàn)
static void partSort(int[] array, int left, int right) {
if (array != null && array.length > 0) {
if (left >= right)
return;
// 找出中間索引
int center = (left + right) / 2;
// 對左邊數(shù)組進(jìn)行遞歸
partSort(array, left, center);
// 對右邊數(shù)組進(jìn)行遞歸
partSort(array, center + 1, right);
//合并
megre(array, left, center, right);
}
}```
/**
- 將左右兩邊有序的數(shù)據(jù)進(jìn)行合并
*/
static void megre(int[] array, int left, int center, int right) {
if (array != null && array.length > 0) {
// 臨時(shí)數(shù)組
int[] tmpArray = new int[array.length];
// 右數(shù)組第一個(gè)元素索引
int mid = center + 1;
// tag 記錄臨時(shí)數(shù)組的索引
int tag = left;
// 緩存左數(shù)組第一個(gè)元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
if (array[left] <= array[mid]) {
tmpArray[tag++] = array[left++];
} else {
tmpArray[tag++] = array[mid++];
}
}
// 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while只會執(zhí)行其中一個(gè)）
while (mid <= right) {
tmpArray[tag++] = array[mid++];
}
while (left <= center) {
tmpArray[tag++] = array[left++];
}
// 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
// （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）
while (tmp <= right) {
array[tmp] = tmpArray[tmp++];
}
}
}
**2.非遞歸實(shí)現(xiàn)**
非遞歸思想: 將數(shù)組中的相鄰元素兩兩配對懈费。用merge函數(shù)將他們排序畦贸，構(gòu)成n/2組長度為2的排序好的子數(shù)組段，然后再將他們排序成長度為4的子數(shù)組段，如此繼續(xù)下去薄坏，直至整個(gè)數(shù)組排好序趋厉。性能由于遞歸實(shí)現(xiàn)
static void megeringSort(int[] array) {
int len = 1;
//程序邊界的處理非常重要
while (len <= array.length) {
for (int i = 0; i + len <= array.length - 1; i += len * 2) {//len 1 2 4 8... ...
int low = i, mid = i + len - 1, high = i + len * 2 - 1; //計(jì)算每次區(qū)間的左中右索引
if (high > array.length - 1) high = array.length - 1;
megre(array, i, mid, high);//執(zhí)行合并
}
len *= 2;
}
}```
