[排序] 快速排序

快速排序动态过程演示

快排的思路很简单, 选择一个基准元素, 把比这个元素大的放到右边, 小的放到左边, 这样就分成了两组
然后对左边的那一组和右边的那一组分别再进行上面的操作
递归进行,如果一组元素的长度为1, 就是递归的出口了

考试时候一般要求给出快速排序分划交换的过程

开始: 50, 79, 8, 56, 32, 41, 85, 26, 70

要注意由于教科书上采用的是两个指针从左右扫描分组的交换策略
因此在排序的过程中并不是简单地分成两组
顺序需要与程序实际运行的一致
这也是快排不稳定的原因吧
如果采取新建数组来分别存储两个分组
那么快排是稳定的
只是空间复杂度会更高一些

第一趟: [26, 8,41, 32 ] 50 [56, 85, 79, 70]
第二趟: [8] 26 [41, 32] 50 56 [85, 79, 70]
第三趟: 8 26 [32] 41 50 56 [70, 79] 85
第四趟: 8 26 32 41 50 56 70 [79] 85
第五趟: 8 26 32 41 50 56 70 79 85

JavaScript实现如下:

/*
 * 快速排序, 不使用另外的数组, 在原数组上原地排序
 *
 * @param array - 待排序的数组
 * @param start - 排序的起始位置下标
 * @param end - 排序的结束位置下标
 */
function quickSort(array, start, end)
{
    // 递归出口
    if(end <= start)
    {
        return
    }

    const datum = array[start] // 取最左边的元素作为基准变量
    let left = start // 左指针
    let right = end + 1 // 右指针
    while(left < right)
    {
        // 从左边开始向右找一个比基准元素大的元素, 注意要防止越界
        left ++
        while(array[left] < datum && left < end)
        {
            left ++
        }

        // 从右边开始向左找一个比基准元素小的元素
        // 向左寻找的过程中不会越界, 临界情况是右指针移动到基准元素位置
        right --
        while(array[right] > datum)
        {
            right --
        }

        // 交换这两个元素
        if(left < right)
        {
            swap(array, left, right)
        }
    }
    
    // 临界情况下, 右指针移动到基准元素位置
    // 这个时候, 就不必再交换基准元素了, 直接分组即可
    // 左边的那一组元素个数肯定为 -1, 会直接到达递归出口
    if(datum < right)
    {
        // 交换基准元素, 将原数组分成两组
        swap(array, datum, right)
    }


    // 分别对两组进行递归
    quickSort(array, start, right - 1)
    quickSort(array, right + 1, end)
}