文章结构
- 归并排序
- 快速排序
- 源码
1. 归并排序
1.1 什么是归并排序
归并排序的思想是：将待排序的区间平分成两个子区间，先对两个子区间进行排序，然后再将排好序的两个子区间合并成一个有序序列。而对子区间的排序也同样遵循这个思想
1.2 动画演示
1.3 代码实现
private static void sort(int[] a, int head, int tail) {
/**
* 递推公式：sort(a,head,tail)=merge(sort(a,head,m),sort(a,m+1,tail))
* 退出条件：head=tail
*/
if (head == tail) {
return;
}
int mid = (head + tail) / 2;
//对左右两个区间排序
sort(a, head, mid);
sort(a, mid + 1, tail);
//将排序好的左右两个区间合并起来
merge(a, head, tail, mid);
}
1.4 归并排序过程图解
1.5 性能分析
时间复杂度
使用递归树来分析归并排序的时间复杂度，递归树的最大深度为log2(n)，每一层的比较次数为n，所以递归排序的时间复杂度在各种情况下都是O(nlogn)。
空间复杂度
递归排序过程中需要借助额外的空间来归并两个有序的序列，这个空间的最大长度等于带排序序列的长度，所以空间复杂度是O(n)
是否稳定
归并排序过程中不存在元素交换位置的情况，所以归并排序是稳定排序
2. 快速排序
2.1 什么是快速排序
快速排序的思想是：在要排序的区间选择任意的一个点作为分区点，遍历区间，将小于分区点的数据都排到分区点的左边；将大于分区点的数据都排到分区点的右边。这样经过一轮排序之后分区点的左边的数据都小于等于它，分区点右边的顺序都大于等于它，分区点的位置就确定了。然后再以相同的方式对左右两个区间进行排序，直到分区区间只含有一个元素位为止。
2.2 代码实现
private static void sort(int[] a, int left, int right) {
/**
* 递推公式：sort(a,p,r)=sort(a,p,m-1)+sort(a,m+1,r)
* 结束条件：head>=tail
*/
if (left < right) {
int low = left;
int hight = right;
int pivot = a[low];
//找到分区点的位置
while (low < hight) {//有元素之间的位置交换，所以不是稳定排序
while (low < hight && a[hight] >= pivot) {
hight--;
}
a[low] = a[hight];
while (low < hight && a[low] <= pivot) {
low++;
}
a[hight] = a[low];
}
a[low] = pivot;
//对左右两个分区进行排序
if (left + 1 < low) {
sort(a, left, low - 1);
}
if (right - 1 > low) {
sort(a, low + 1, right);
}
}
}
2.3 过程分析
我们来分析一下一趟快速排序的过程
- 使用一个索引low指向待排序区间的最低位；使用一个索引hight指向待排序区间的最高位
- 选择待排序区间的最低位作为分区点pivot
- 从后往前遍历，移动hight索引，直到找到一个比分区点pivot小的值，将hight指向的值赋值给low指向的位置
- 然后从前往后遍历，移动low索引，直到找到一个比分区点pivot大的值，将low指向值赋值给hight指向的位置
- 重复3,4步骤，直到low=hight，此时low就是分区点在序列有序之后的位置
- 将pivot赋值给low，此时low前面的数据都比pivot小，low后面的数据都比pivot大，接着分别对low的前后两个区间执行这个排序过程
2.4 性能分析
时间复杂度
- 最好时间复杂度：O(nlogn)，当每次分区点都刚好在待排序区间的正中间时
- 最坏时间复杂度：O(n^2)，当每次分区都是1,n-1时，总共要n次分区
- 平均是否复杂度：O(nlogn)，只有在极端情况下才会出现O(n^2)，所以它的平均时间复杂度还是O(nlogn)
空间复杂度
这里只使用了几个零时空间来存储中间值，所以空间复杂度是O(1)
是否稳定
快排不是稳定排序，因为在上面的第3,4步中存在交换元素位置的情况
2.5 快速排序的应用
如何在O(n)的时间复杂度下从无序序列中找出第K大的数
使用快速排序查找第K大的数的思路：
一趟快排之后，分区点左边的数据都小于分区点，分区点右边的数据都大于分区点，也就是分区点的排序已经排好了。如果此时分区点正好是第k大的数，则直接返回这个数即可。如果分区点的位置倒数倒数第k个数之前，则在右边序列中继续查找；如果分区点的位置在倒数第k个数之后，则在前面的序列中查找。
代码实现
/**
* 在O(n)的时间复杂度内找出无序数组中的第K大数
*
* @param array
* @param k
*/
public static int getMaxK(int[] array, int k) {
if (array == null || array.length < k) {
return Integer.MIN_VALUE;
}
return sort(array, 0, array.length - 1, array.length - k);//计算第k大数在序列中的位置：array.length - k
}
private static int sort(int[] a, int left, int right, int index) {
if (left < right) {
int low = left;
int hight = right;
int pivot = a[low];
//找到分区点的位置
while (low < hight) {
while (low < hight && a[hight] >= pivot) {
hight--;
}
a[low] = a[hight];
while (low < hight && a[low] <= pivot) {
low++;
}
a[hight] = a[low];
}
a[low] = pivot;
if (low == index) {//分区点的位置就是要查找的第K大数
return pivot;
} else if (low < index) {//分区点的位置在要查找的位置的左边
return sort(a, low + 1, right, index);
} else if (low > index) {//分区点的位置在要查找的位置的右边
return sort(a, left, low - 1, index);
}
}
return a[left];
}
测试用例
@Test
public void testGetMaxKth() {
int size = 10;
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = new Random().nextInt(size * 10);
}
print(array, "org:");
int index = 5;
System.out.println("the " + index + "th:" + QuickSort.getMaxK(array, index));
print(array, "sorted:");
}
private static void print(int[] array, String s) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < array.length; i++) {
builder.append(array[i] + ",");
}
System.out.println(s + builder.toString());
}
输出结果
org: 92,71,57,88,46,79,85,48,56,47,
the 5th: 71
sorted: 46,47,56,48,57,71,79,85,88,92,
我们看sorted之后的结果，71确实是无序序列的第5大数，它左边的都比它小，它右边的都比它大
时间复杂度分析
我们看一种情况，假设每次分区都在中间点上，然后我们直到最后一趟快排才找到第K大数，这个时候的时间复杂的是多少呢？我们总共经历了log2(n)趟快排，总共经历的比较次数是n+n/2+2/4+n/8……+n/n=2*n-1（等比数列求和），所以时间复杂度还是O(n)
3. 源码
源码和测试用例请查看github之排序
说明
文中图片来源：极客时间，王争《数据结构与算法之美》
