快排基本步骤

基本思想

时间复杂度: $logN^N$ 或者 $N*logN$

采用分治的方法

• 从数组中找出一个数作为基数
• 将大于这个基数的数放在右边，小于基数的数放在左边
• 重复上述步骤，直到各区间只有一个数

采用挖坑填数的思想

• i=L，j=R；讲基数挖出形成第一个坑a[i]
• j--后向前找比他小的数，找到后将此数填到a[i]中
• i++从前往后找比基数大的，找到后将此数填到a[j]中
• 重复上述步骤，直到i==j

核心代码

挖坑法

     public int  AdJust(int arr[],int l,int r){
        int i = l,j=r;
        int standard = arr[l];
        while (i<j) {
            while (i < j && arr[j] > standard)
                j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i] < standard)
                i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = standard;
        return i;
    };

再采用分治法

    void quickSort(int arr[],int l,int r){
        if (l<r){
            int x = AdJust(arr,l,r);
            quickSort(arr,l,x-1);//中间的不用再排序
            quickSort(arr,x+1,r);
        }
    }

整合上面2个代码

void QuickSort(int arr[], int l, int r) {
    if (l < r) {
        int i = l, j = r;
        int standard = arr[l];
        while (arr[j] >= standard && i < j) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (arr[i] < standard && i < j) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
        arr[i] = standard;
        QuickSort(arr, l, i - 1);
        QuickSort(arr, i + 1, r);
    }
}

快排-挖坑排序参考地址---MoreWindows