歸并排序
什么是歸并排序：圖解歸并排序
歸并排序有兩種實(shí)現(xiàn)方式塔次，一是基于遞歸，而是基于迭代
1）基于遞歸的歸并排序：
public class MergeSort {
public static void main(String[] args) {
int[] a = {8, 4, 5, 7, 1, 3, 6, 2};
sort(a);
System.out.println("排序以后: " + Arrays.toString(a));
}
/**
* 構(gòu)建一個(gè)和排序數(shù)組長(zhǎng)度一樣的臨時(shí)數(shù)組
* @param a 需要進(jìn)行排序的算法
* */
private static void sort(int[] a) {
int[] temp = new int[a.length];
sort(a, 0, a.length - 1, temp);
}
private static void sort(int[] a, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
sort(a, left, mid, temp); //左邊遞歸排序叹卷，使得左子序列有序
sort(a, mid + 1, right, temp); //右邊遞歸排序钞支，使得右子序列有序
merge(a, left, mid, right, temp); //將兩個(gè)有序子數(shù)組合并
}
}
private static void merge(int[] a, int left, int mid, int right, int[] temp) {
int i = left;//左序列指針
int j = mid+1;//右序列指針
int t = 0;//臨時(shí)數(shù)組指針
while (i<=mid && j<=right){
if(a[i]<=a[j]){
temp[t++] = a[i++];
}else {
temp[t++] = a[j++];
}
}
//將左邊剩余元素填充進(jìn)temp中
while(i<=mid){
temp[t++] = a[i++];
}
//將右序列剩余元素填充進(jìn)temp中
while(j<=right){
temp[t++] = a[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數(shù)組中
while(left <= right){
a[left++] = temp[t++];
}
}
}
基于遞歸的歸并算法實(shí)現(xiàn)思路：將數(shù)組對(duì)半對(duì)半分進(jìn)行遞歸直到只有一個(gè)數(shù)組元素
基于遞歸的歸并排序特別浪費(fèi)空間验夯，并且如果數(shù)據(jù)量特別大的話，它的效率將特別低
2)歸并排序的優(yōu)化：采用迭代代替遞歸
public class MergeSortOptimized {
public static void main(String[] args) {
int[] a = {1, 3, 5, 7, 9, 2, 4, 6, 10, 0};
mergeSort(a);
System.out.println("排序后: " + Arrays.toString(a));
}
/**
* mergeSort每次負(fù)責(zé)計(jì)算步長(zhǎng)
*
* @param a 需要進(jìn)行排序的數(shù)組
*/
private static void mergeSort(int[] a) {
int k = 1;
int length = a.length;
while (k < length) {
mergePass(a, k, length);
k *= 2;
}
}
/**
* 將兩個(gè)長(zhǎng)度為k的相鄰數(shù)組進(jìn)行排序
*
* @param a 需要進(jìn)行排序的數(shù)組
* @param k 相鄰的元素個(gè)數(shù)
* @param len 數(shù)組的長(zhǎng)度
*/
private static void mergePass(int[] a, int k, int len) {
int i = 0;
//從前往后,將2個(gè)長(zhǎng)度為k的子序列合并為1個(gè)
while (i < len - 2 * k + 1) {
merge(a, i, i + k - 1, i + 2 * k - 1);
i += 2 * k;
}
//如果存在不足以兩兩merge的數(shù)組
if (i < len - k) {
merge(a, i, i + k - 1, len - 1);
}
}
private static void merge(int[] a, int left, int mid, int right) {
//temp數(shù)組用于暫存合并的結(jié)果
int[] temp = new int[right - left + 1];
//int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
//暫存數(shù)組的下標(biāo)
int t = 0;
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
temp[t++] = a[i++];
} else {
temp[t++] = a[j++];
}
}
//將左邊剩余元素填充進(jìn)temp中
while (i <= mid) {
temp[t++] = a[i++];
}
//將右序列剩余元素填充進(jìn)temp中
while (j <= right) {
temp[t++] = a[j++];
}
t = 0;
//將temp中的元素全部拷貝到原數(shù)組中
while (left <= right) {
a[left++] = temp[t++];
}
}
}
基于迭代的遞歸算法實(shí)現(xiàn)思路憔恳，相鄰兩個(gè)數(shù)組進(jìn)行遞歸瓤荔，相鄰四個(gè)數(shù)組進(jìn)行遞歸，依次類推喇嘱，不采用遞歸而是采用循環(huán)的方式來代替
遞歸算法的時(shí)間復(fù)雜度為o(nlogn)
迭代歸并排序時(shí)茉贡，如果mid用(left+right)/2而不是使用i + k - 1，排序結(jié)果將不正確：待解決
