快速排序算法的基本思路

• 任意选取一个基准数k
• 小于k的数放在k的左边，大于k的数放在k的右边
• 再对k左边的子数组和右边的子数组排序，直到子数组只有一个数为止【递归】

对于第二步，有很多种方法，下面是快排的提出者C.R.A.Hoare的方法：

hoare的交换排序法

• 选取第一个数为基准数，
• q指针从最右边开始往左移动，当q的值小于基准数时，停下
• p指针从左边开始往右移动，当p的值大于基准数时，停下
• 交换p和q的值
• 然后继续交替移动，直到p和q指向同一个数
• 交换此数和基准数
• 完成

代码示例

/**
 * 快速排序
 * @param arr 要排序的子数组
 * @param left 子数组左下标
 * @param right 子数组右下标
 */
function quickSort(arr: number[], left: number, right: number){
    //当左右下标相等时，说明数组中只有一个数了，则不需要排序
    if (left >= right){
        return;
    }
    let k = hoareSort(arr, left, right); //把第一个数作为基准数k，先排第一趟，第一趟完后基准数左边的数全部小于k，右边的数全部大于k
    quickSort(arr, left, k - 1);         //然后把k左边的子数组再排一遍
    quickSort(arr, k + 1, right);        //把k右边的子数组再排一遍
}

/**
 * hoare的交换排序法
 * 选取第一个数为基准数，
 * q指针从最右边开始往左移动，当q的值小于基准数时，停下
 * p指针从左边开始往右移动，当p的值大于基准数时，停下
 * 交换p和q的值
 * 然后继续移动，直到p和q指向同一个数
 * 交换此数和基准数
 * 完成
 */
function hoareSort(arr: number[], left: number, right: number): number{
    let k = left;
    let p = left;
    let q = right;
    while (p < q){
        while (p < q && arr[q] >= arr[k]){
            q--;
        }
        while (p < q && arr[p] <= arr[k]){
            p++;
        }
        let t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }
    let t = arr[k];
    arr[k] = arr[p];
    arr[p] = t;
    return p;
}

quickSort(arr, 0, arr.length - 1)