归并排序
什么是归并排序：图解归并排序
归并排序有两种实现方式，一是基于递归，而是基于迭代
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));
}
/**
* 构建一个和排序数组长度一样的临时数组
* @param a 需要进行排序的算法
* */
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); //将两个有序子数组合并
}
}
private static void merge(int[] a, int left, int mid, int right, int[] temp) {
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(a[i]<=a[j]){
temp[t++] = a[i++];
}else {
temp[t++] = a[j++];
}
}
//将左边剩余元素填充进temp中
while(i<=mid){
temp[t++] = a[i++];
}
//将右序列剩余元素填充进temp中
while(j<=right){
temp[t++] = a[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
a[left++] = temp[t++];
}
}
}
基于递归的归并算法实现思路：将数组对半对半分进行递归直到只有一个数组元素
基于递归的归并排序特别浪费空间，并且如果数据量特别大的话，它的效率将特别低
2)归并排序的优化：采用迭代代替递归
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每次负责计算步长
*
* @param a 需要进行排序的数组
*/
private static void mergeSort(int[] a) {
int k = 1;
int length = a.length;
while (k < length) {
mergePass(a, k, length);
k *= 2;
}
}
/**
* 将两个长度为k的相邻数组进行排序
*
* @param a 需要进行排序的数组
* @param k 相邻的元素个数
* @param len 数组的长度
*/
private static void mergePass(int[] a, int k, int len) {
int i = 0;
//从前往后,将2个长度为k的子序列合并为1个
while (i < len - 2 * k + 1) {
merge(a, i, i + k - 1, i + 2 * k - 1);
i += 2 * k;
}
//如果存在不足以两两merge的数组
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数组用于暂存合并的结果
int[] temp = new int[right - left + 1];
//int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
//暂存数组的下标
int t = 0;
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
temp[t++] = a[i++];
} else {
temp[t++] = a[j++];
}
}
//将左边剩余元素填充进temp中
while (i <= mid) {
temp[t++] = a[i++];
}
//将右序列剩余元素填充进temp中
while (j <= right) {
temp[t++] = a[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right) {
a[left++] = temp[t++];
}
}
}
基于迭代的递归算法实现思路，相邻两个数组进行递归，相邻四个数组进行递归，依次类推，不采用递归而是采用循环的方式来代替
递归算法的时间复杂度为o(nlogn)
迭代归并排序时，如果mid用(left+right)/2而不是使用i + k - 1，排序结果将不正确：待解决
