简介

时间复杂度：$O(nlogn)$

快速排序是不稳定算法

步骤

分为三个过程：

  1. 将集合划分为两部分（保证大小关系即可，partition函数）
  2. 递归的在两个划分好的部分分别进行快排
  3. 不用合并，因为此时集合已经完全有序

Java实现

public static void quickSort(int[] data, int low, int high) throws Exception {
    if(low == high){
        return;
    }
    if(low < high){
        int partition = partition(data, data.length, low, high);
        quickSort(data, low, partition-1);
        quickSort(data, partition+1, high);
    }
}
private static int partition(int data[], int length, int low, int high) throws Exception {
    if(data == null || data.length<= 0 || low < 0 || high >= length ){
        throw new Exception("Invalid Parameters");
    }
    // 默认选择首位作为枢轴
    int position = data[low];
    while (low < high){
        while (low< high && data[high] >= position){
            high--;
        }
        data[low] = data[high];
        while (low<high && data[low] <= position){
            low++;
        }
        data[high] = data[low];
    }
    data[low] = position;
    return low;
}

References