归并排序
原理
归并排序是用了分而治之的思想，原理对照下边我画的图看很简单，将数组分成前后两部分，然后分别对这两部分排序，排序好之后再合并起来。
归并排序
而在代码中我们需要用到递归来实现。众所周知，递归先要找到递推公式和终止条件。
-
递推公式：
sort(start, end) = merge(sort(start, mid), sort(mid + 1, end); -
终止条件：
start >= end
其中：
mid = (start + end ) / 2;-
sort方法是将数组拆分成两部分分别排序 -
merge方法是将两个排好序的数组合并成一个数组
代码
private static void sortArray(int[] arr) {
// 创建与 arr 等长的临时数组
int[] temp = new int[arr.length];
// 调用排序算法
sort(arr, 0, arr.length - 1, temp);
}
private static void sort(int[] arr, int start, int end, int[] temp) {
// 递归终止条件 拆到数组只有一个元素时，start = end
if (start >= end) {
return; // 结束递归
}
// 假设数组是｛0，1｝,start = 0, end = 1, mid = 0
int mid = (start + end) / 2;
// 对左边排序
sort(arr, start, mid, temp);
// 对右边排序
sort(arr, mid + 1, end, temp);
// 合并
merge(arr, start, mid, end, temp);
}
private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
// i，j 为左列、右列各自第一个元素下标， k 为 temp 临时数组对应下标
int i = start, j = mid + 1, k = start;
// 顺序依次比较左、右列的元素，从小到大放入 临时数组对应位置
// 如果任一列元素遍历完，就停止遍历
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 把左列或右列剩下没有进行遍历赋值的元素赋值到 temp 中
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= end) {
temp[k++] = arr[j++];
}
// 把本次合并区间排列好的元素从temp赋值到arr中
for (int x = start; x <= end; x++) {
arr[x] = temp[x];
}
}
分析
- 稳定性：合并时如果有相等的元素，先将前列的数据放入temp数组，保证有序性，是稳定的排序算法。
- 空间复杂度：需要一个临时数组 temp 来存放数据，空间复杂度O(n)。
- 时间复杂度：具体算法不写了，归并排序的时间复杂度与数组的有序程度无关，不管最好、最坏还是平均，时间复杂度都是O(nlogn)。
快速排序
原理
快速排序和归并排序很相似，也用到了分治、递归，甚至连递推公式都是一样的。但思路其实并不相同，快排的主要思想是，我们随便选择一个数组中的元素作为中间点，遍历数组，将小于中间点的元素放在左边，大于中间点的元素放在右边，中间点放在中间。这样继续对前半部分和后半部分分别做一样的操作，直到无法分隔，这时数组就是有序的了。如图所示：一般情况选末尾的元素作为中间点。
快排原理
我们继续深入思考，具体如何实现这个过程呢？不考虑空间消耗，可以每次拆分都创建两个临时数组，遍历将元素挨个放进去，然后再合并回来。
我们可以发现，归并排序并没有办法做到本地排序，那快速排序有没有办法呢？来看下边这张图，用到了和选择排序有点类似的技巧。以末尾的5为区分，遍历数组比较，比它小的插在前边，比它大的插在后边。
但往数组中插入元素需要把很多元素向后移一位，很耗时。同样我们可以用交换代替插入，具体过程如图：选中末尾的5为中间点，用游标i标记小于5的部分，游标k表示当前遍历元素。拿k指向的元素和5去比较，如果小于5，就和i指向的元素交换位置。继续遍历，最后将k指向的5和i指向的元素交换位置，让中间元素位于两个部分的中间。
从这个过程中也可以看出，快排不是一个稳定的排序算法。
代码
private static void sortArray(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int start, int end) {
// 递归结束条件
if (start >= end) {
return;
}
// 分区，返回分区中间点下标
int p = part(arr, start, end);
// 继续分别排序中间点前后数组
sort(arr, start, p - 1);
sort(arr, p + 1, end);
}
private static int part(int[] arr, int start, int end) {
// 标记小于中间点区间的结尾
int i = start;
// 选尾部元素为中间点
int p = arr[end];
// 遍历，如果比中间点小，就插入小于区间的末尾
for (int k = start; k < end; k++) {
if (arr[k] < p) {
swap(arr, i, k);
i++;
}
}
// 遍历结束后把中间点放到它应该在的位置
swap(arr, i, end);
return i;
}
/**
* 数组元素交换位置
*/
private static void swap(int[] arr, int i, int k) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
分析
- 稳定性：非稳定排序算法。
- 空间复杂度：利用上文图中的巧妙算法，我们做到了本地排序，空间复杂度O(1)。
- 时间复杂度：基本同归并排序，只有在极端情况下（比如已经是有序数组，我们选择最后一个元素作为中间点）会退化成O(n²)。在大部分情况下，时间复杂度是O(nlogn)
结语
代码一定要自己想着写一遍，会理解、记忆的更清楚。原理看着简单，但转为代码时就会变得一头雾水。另外很多关于边界的判断一不留神就出bug了。
网友评论