改进版快速排序:随机化快速排序算法
上篇我们介绍了快速排序算法的基本实现,但是这个基本实现有一个很大的问题。
一个100万大小的完全随机的数组,测试结果:
QuickSort: 1000000 true 88ms
MergeSort: 1000000 true 198ms
一个100万大小的近乎有序的数组,测试结果:
QuickSort: 1000000 true 18892ms
MergeSort: 1000000 true 43ms
对近乎有序的数组排序时,上面实现的快速排序算法效率很差。从上面的两组测试结果中可以看出,快速排序算法的基本实现比归并排序算法慢了太多了。这是为什么呢?我们下面来进行分析一下。
前面文章介绍过,归并排序之所是O(nlogn)级别的算法,是因为在每次排序的时候都将原来的数组一分为二,进一步再将每一个子数组一分为二。以此类推,那么整个层数是logn层。每一层的归并过程是O(n)级别的时间复杂度,所以整个归并算法的就是O(nlogn)级别的时间复杂度。
事实上,我们上面实现的快速排序算法,也是不断的将整个数组一分为二的过程,只不过这个分法不一样。对于快速排序算法来说,我们是需要找到一个标定点,对这个标定点左边和右边两个数组分别进行排序。这样一来快速排序就存在一个和归并排序非常大的不同,归并排序可以保证每次都是平均将整个数组一分为二,而快速排序就没有这个保证。
快速排序分出来的两个子数组可能是一大一小的,对子数组进一步分割的时候,依然存在这种情况。由于这种情况,快速排序调用递归的过程所生成的递归树,它的平衡度就会比归并排序要差,并且我们不能完全保证这个递归树的高度就是logn,它很有可能比logn要大。
最差的情况是什么,事实上最差的情况就是我们之前测试的,当整个数组近乎有序的情况。
我们来看一下,如果整个数组完全有序,会发生什么?
每次都使用最左边的元素值作为标定点,当整个数组完全有序的时候,没有任何元素小余标定点的元素,所有的元素都要大于它。那么生成的递归树左边就没有东西,只有右边这部分。对于右边这部分我们找的标记点又是它最左边的元素,在数组有序的情况下,最左边的这个元素又是最小的元素。于是又出现了这棵树的子树左边没有任何元素,只有右边的元素。以此类推,在这种情况下,整个递归树的高度为n,这个递归树同时也可以看做是链表。整个递归树的高度是n,在每一层处理的时候是O(n)的时间复杂度,此时快速排序算法就退化成了一个O(n^2)级别的算法。这也就是我们之前的测试中,为什么在数据近乎有序的情况下,快速排序这么慢的原因。
那么怎么改变这种情况呢,其实非常简单。我们现在是固定的选用最左边的元素,作为标定元素。然而我们希望的是尽可能的选择整个数组中间的元素,作为标定元素。我们不能非常快速准确的定位中间元素,怎么办?其实我们只需要随机选着一个元素就可以了,当我们随机选着一个元素,作为标记元素的时候,我们可以用数学的方法证明出来,此时快速排序的时间复杂度的期望值是O(nlogn)。这里是期望值是O(nlogn),而不代表每次一定是O(nlogn)。
大家可以想象一下,使用随机的标记元素时,退化成O(n^2)的可能性是非常非常低的。这是因为此时如果我们要让快速排序退化成为O(n^2)级别的算法,在第一层的时候我们就要正好选到最左边的元素,它的概率是1/n。在第二层的时候我们就要正好选中该层最左边的元素,它的概率是1/(n - 1)。以此类推,每层都要正好选中改层最左边元素的概率是(1/n)*(1/(n - 1))*(1/(n - 2))...(1/2)*1。当n非常大的时候,得到的概率值是几乎为0。
优化后的代码如下:
package com.zeng.sort;
import java.util.Arrays;
public class QuickSort {
public void quickSort(int[] arr){
quickSort(arr, 0, arr.length - 1);
}
/**
* 使用递归,对arr[left...right]部分进行快速排序,区间是前闭后闭的
* @param arr
* @param left
* @param right
*/
private void quickSort(int[] arr, int left, int right){
// if(left >= right){
// return;
// }
//优化:对元素量比较少的部分,用插入排序法进行优化
if(right - left <= 15){
insertionSort(arr, left, right);
return;
}
//先添加一些规划数组
int p = partition(arr, left, right);
//再对两部分数组分别做快速排序
quickSort(arr, left, p - 1);
quickSort(arr, p + 1, right);
}
/**
* 插入排序算法,对数组中子数组[left, right]进行排序.
* @param arr
* @param left
* @param right
*/
private void insertionSort(int[] arr, int left, int right){
for(int i = left + 1; i <= right; i ++){
int e = arr[i];
int j = i;
for(; j > left && arr[j - 1] > e; j --){
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
/**
* 对arr[left...right]部分进行partition操作
* @param arr
* @param left
* @param right
* @return 返回p,使得arr[left...p-1] < arr[p]; arr[p+1...right] > arr[p]
*/
private int partition(int[] arr, int left, int right){
//优化近乎有序数组的排序效率,避免出现O(n^2)级别的时间复杂度。
swap(arr, left, (int)(Math.random() * (right - left + 1) + left));
int v = arr[left];
//arr[left+1...j] < v; arr[j+1...i) > v
//初始化两个为空的区间arr[left+1...j]和arr[j+1...i)
//使得整个程序从初始的情况下,都满足这个条件。
int j = left;
for(int i = left + 1; i <= right; i++){
if(arr[i] < v){
swap(arr, j + 1, i);
j++;
}
}
swap(arr, left, j);
return j;
}
/**
* 交换数组中两个元素的值
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
这里对第二条优化后的快速排序和上篇文章的归并排序做对比测试
一个100万大小的完全随机的数组,测试结果:
QuickSort: 1000000 true 101ms
MergeSort: 1000000 true 206ms
一个100万大小的近乎有序的数组,测试结果:
QuickSort: 1000000 true 41ms
MergeSort: 1000000 true 41ms
从这个测试结果可以看出,随机化快速排序对近乎有序数组的排序效率,提升特别大。
在这里我们实际上编写了一个随机算法,所谓的随机算法就是不能保证算法一定非常快,或者一定是正确的,但是可以保证算法在99.99%(非常高的概率)的情况下,都能非常快并且非常准确的得到结果。
此时快速排序的最坏时间复杂度依然是O(n^2),但是退化到O(n^2)级别的时间复杂度的概率是极其极其低的,近乎为0。当然了对于使用这样一种随机化的方法,快速排序的时间复杂度的期望值就变成了O(nlogn),这个数学证明是非常复杂的,这里就不展开说明了,有兴趣的可以去查阅一些算法分析的文章。
这里还有一种情况,当我们对拥有大量重复键值对的数组进行排序时,情况又会怎么样呢?下篇文章中就继续优化我们的快速排序。