快速排序思想

取序列中的第一个元素,并将它移动到它应该处在的位置上
并且它前面的元素都小于它,后面的元素都大于它
之后再对前后两部分进行相同逻辑的递归,整个数组就排好序了

逻辑处理问题

这个逻辑被称为Partition
用指针 l表示第一个元素 v 的位置
用指针j表示小于v区间的最后一个元素的位置
用指针i表示遍历这个序列的光标位置
那么arr[l+1..j] < v; arr[j+1..i-1] > v
当i指向的元素 arr[i] >= v ,光标后移(i++)即可
而当 arr[i] < v,则 j+1与i位置做交换,j的位置和光标都后移
当这个过程走完,将v与j交换位置即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void quickSort(int[] arr, int l, int r) {
    if (l >= r) return;
    __partition(arr, l, r);
}

private static void __partition(int[] arr, int l, int r) {
    int j = l;
    int v = arr[l];
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v)
            BaseArrayUtil.swap(++j, i, arr);
    }
    arr[l] = arr[j];
    arr[j] = v;
    quickSort(arr, l, j - 1);
    quickSort(arr, j + 1, r);
}

数组有序

根据快速排序的逻辑,当整个数组有序的时候.那么每个元素一开始就在它应该放到的位置上
故而数组每次都被拆分为1、n-1； 第一个元素遍历的数组范围为n-1,第二个元素为n-2....
故而对于近乎有序的数组,快速排序需要耗费的时间为O(n^2)
解决方案也很简单,只需要在partition过程之前让l..r之间的随机一个元素与l作交换即可让数组作拆分
1
2
3
4
5
private static void __partition(int[] arr, int l, int r) {
    int random = (int) (Math.random() * (r - l + 1)) + l;
    BaseArrayUtil.swap(l, random, arr);
   	...
}
这样做最差的情况仍然是O(n^2),那就是每次随机又随到了第一个
但是几率极低,最差的情况为1/(n-1) * 1/(n-2)...概率几乎为0
从数学的角度思考,快速排序的timeComplexity也为n*log(n)

数组取值范围小

问题 : 一百万数据 0-100取值,为何会爆栈? 0-1000就不会了