归并排序
2020-04-04 本文已影响0人
范柏柏
图解
归并排序.png
思想：分治思想
分治思想是算法常用的思想。实现方式通常是递归。
分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突
归并排序思路
递推公式
既然设计到递归。下意识就要想使用递归的两个必要条件
- 递推公式
- 递归退出条件
其实递推公式简单。如图所示。
step1: 拆分
将数组从中间分为左右两部分。再将分好的左右两部分再分成各自的左右两部分。直到左右两部分都只有一个元素。
step2: 合并
递归的第一层是两个数的排序。比较大小就好。
递归的其他层，是两个有序数组的排序。
所以归并排序其实就是将一个无序的数组，变成若干个有序数组，接下来就是有序数组的排序了
step3: 有序数组排序
两个有序数组怎么排序。借助另一个数组。
开一个新数组tmp，大小为两个有序数组的总和。
从头遍历两个有序数组，谁小，将小的元素放入tmp，指针向后移动一位。
有一个数组走到最后，退出，将另个数组的剩余元素按序放入tmp
结束
有了核心思想，现给出递推公式，和退出条件
- 递推公式： mergeSort(start…end) = merge(mergeSort(start…middle), mergeSort(middle…end))
- 退出条件：当start >= end的时候退出
- merge函数就是step3那步的有序数组排序
代码
public static void mergeSort(int[] a, int startIndex, int endIndex) {
/**
* 思路：
* 1、从终点分为左右两部分，对这两部分进行排序
* 2、递归，一直递归到左右都各有一个元素
* 3、从最后一个元素开始排序，两个元素两个元素排，然后再两个有序数组两个有序数组排
*/
/**
* 递归的结束条件 左index >= 右index
* 走到这一步说明，左index与右index相邻，左右两部分都只有一个元素
*/
if(startIndex >= endIndex) {
return;
}
/**
* 将start-end 拆成 左右两个start-end
*/
int middle = startIndex + (endIndex - startIndex) / 2;
int leftStartIndex = startIndex;
int leftEndIndex = middle;
int rightStartIndex = middle + 1;
int rightEndIndex = endIndex;
/**
* 将左右两个数组 接着递归 直到触发递归退出条件
*/
mergeSort(a, leftStartIndex, leftEndIndex);
mergeSort(a, rightStartIndex, rightEndIndex);
/**
* 递归结束，合并左右两部分
*
* 递归第一步：两个元素排序
* 递归最后一步：两个有序数组排序
*/
merge(a, leftStartIndex, leftEndIndex, rightStartIndex, rightEndIndex);
}
public static void merge(int[] a, int leftStartIndex, int leftEndIndex, int rightStartIndex, int rightEndIndex) {
/**
* 思路：
* 1、开一个临时数组，在这个临时数组里做 两个顺序列表的排序
* 2、排好序，拿这个临时数组，覆盖原数组，这样，原数组就是排好序的了
*
* 因为开启了临时数组，所以归并排序并不是原地排序
*/
int[] temp = new int[rightEndIndex - leftStartIndex + 1];
int tmpIndex = 0;
int leftCurrentIndex = leftStartIndex;
int rightCurrentIndex = rightStartIndex;
while (leftCurrentIndex <= leftEndIndex && rightCurrentIndex <= rightEndIndex) {
if (a[leftCurrentIndex] <= a[rightCurrentIndex]) {
temp[tmpIndex++] = a[leftCurrentIndex++];
} else {
temp[tmpIndex++] = a[rightCurrentIndex++];
}
}
/**
* 能跳出一定是左右某一边排完了
* 判断是哪边排完了 直接将另一边顺序放入temp就好
*
* 当左边不满足条件出来的时候，leftCurrentIndex已经++过了，所以得和+1判等
*/
if (leftCurrentIndex == leftEndIndex + 1) {
while (rightCurrentIndex <= rightEndIndex) {
temp[tmpIndex++] = a[rightCurrentIndex++];
}
} else {
while (leftCurrentIndex <= leftEndIndex) {
temp[tmpIndex++] = a[leftCurrentIndex++];
}
}
/**
* 现在temp已经是排好序的了
* 接下来就是用temp覆盖原列表
*/
for (int i = 0; i < rightEndIndex - leftStartIndex; i++) {
a[leftStartIndex + i] = temp[i];
}
}
public static void main(String[] args) {
System.out.println("=============归并排序=================");
int[] list1 = new int[]{4, 5, 6, 7, 1, 2, 4, 9};
mergeSort(list1, 0, list1.length - 1);
System.out.println(Arrays.toString(list1));
System.out.println("======================================");
System.out.println();
}
复杂度分析
时间复杂度
定义求解问题a的时间为T(a)，求解左右两数组的时间为T(b),T(c)，merge的时间为T(merge)
T(a) = T(b) + T(c) + T(merge)
因为bc是a从中间分解的，所以执行时间相同。有序数组的排序时间复杂度是O(n)，所以公式可以转变为
T(n) = 2* T(n/2) + n
来。进一步推导
T(n) = 2 * T(n/2) + n
= 2 * ( 2 * T(n/4) + n/2) + n = 4 * T(n/4) + 2 * n
= 4 * ( 2 * T(n/8) + n/4) + 2n = 16 * T(n/8) + 3 * n
= 8 * ( 2 * T(n/16) + n/8) + 4n = 16 * T(n/16) + 4 * n
= 2^k * T(n/2^k) + k * n
来。去掉常量计算k
T(1) = T(n/2^k)
n / 2^k = 1
2^k = n
k = log2n
将k = log2n 带入时间复杂度求解公式
T(n) = 2^k T(n/2^k) + kn
T(n)=Cn+nlog2n
综上。时间复杂度为：O(nlogn)
空间复杂度
空间复杂度，就看为了实现归并排序，在数组外开了多大的空间就好了。
这个原数组外的空间在这里就是step3中开的新数组tmp。
每次开完就回收，不涉及累加，所以空间复杂度为O(n)
