排序算法——快速排序

原理

快速排序运用了递归的思想。 以升序为例，

1. 在一趟排序过程中，取一个标准值，将小于标准值放到左边，不小于标准值的放到右边，最后返回标准值所在的位置middle
2. 对左边(start ~ middle)部分进行单次排序（递归）
3. 对右边(middle + 1 ~ end) 部分进行单次排序（递归）
4. 对直到start >= end，排序结束。

复杂度分析

平均时间复杂度为O(n*㏒₂n)，每次将数据源对半分
时间复杂度最坏为O(n^2), 数据源一开始就是有序状态，在进行数据源分割的时候总是分为1 和n-1
空间复杂度为 O(㏒₂n)，递归所需栈空间
不稳定

代码实现

public void sort(int[] a){
    qsort(a, 0, a.length - 1);
}

private void qsort(int[] a, int start, int end){
    if (start >= end) {//递归出口
        return ;
    }
    int middle = stepSort(a, start, end);//单次排序
    qsort(a, start, middle);//左边递归
    qsort(a, middle + 1, end);//右边递归
}

/**
 * 单次排序
 * 本次排序结束，左边的值<标准值<=右边的
 * return 标准值所在位置
 **/
private int stepSort(int[] a, int start, int end){
    int std = a[start];
    while (start < end){
        while (start < end && a[end] >= std){//找到右边第一个比标准值小的位置
            end--;
        }
        a[start] = a[end];//放到左侧
        while (start < end && a[start] < std){//找到左边第一个不小于标准值的位置
            start++;
        }
        a[end] = a[start];
    }
    a[start] = std;
    return start;
}