排序算法系列之——快速排序

作为程序员必备课题之一的算法系列中，排序这个最为常见的算法实现也是很有必要掌握的，所以做一个系列的总结，便于交流学习

废话少说，进入正题

如有误，辛苦指正

背景介绍

$\color{#ea4335}{快速排序}$ （Quicksort）是对 $\color{#ea4335}{冒泡排序}$ 的一种改进。

快速排序由 $\color{#4285f4}{C. A. R. Hoare}$ 在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 $\color{#34a853}{递归进行}$ ，以此达到整个数据变成 $\color{#34a853}{有序序列}$ 。 --- 快速排序算法

核心特点

(1)、在所需要排序的集合中，选择一个元素作为"基准"（pivot）。
(2)、然后以这个基准值作为判断依据，小于它则放到他的左边，反之则放到另一边。
(3)、最后对两遍不停的重复步骤2，是的最终只剩下一个元素位置。

举个例子

[ 1, 5, 4, 3, 6, 2, 7 ]

我们随便定一个基准值，假设为3，那么根据核心特点，第一次执行完毕后得到两个数组

小于3的：[ 1, 2 ]
大于3的：[ 5, 4, 6, 7]

将小于3的的数组重复执行步骤，根据核心特点，最后退出的条件是元素为1，所以小于3的数组最终为

[ 1, 2 ]

再将大于3的数组做同样的操作，假设基准值为6得到

小于6的：[ 5, 4 ]
大于6的：[ 7 ]

......
重复操作后最终将所有的数组连接起来即可
此时应该大概了解了快速排序的算法流程，但是对细节还略有模糊，那么我们在结合代码做理解

代码示例

1、我们创建一个排序方法，并接受一个参数，就是我们需要排序的数组

function quickSort( _array ){
    
}

2、我们需要设定一个基准值，并创建两个数组用来存放小于/大于基准值的数的集合

function quickSort( _array ){
    //假设我取了数组中间的数作为基准值，得到他的下标, 我们使用~~来获取值为floor时的整数部分，也可以使用Math.floor()来实现
    var _pivot_index = ~~( _array.length / 2 );
    //基准值
    var _pivot = _array.splice(_pivot_index, 1)[0];
    //我们需要两个数组来存放大于小于基准值的集合
    var _left = [] ,
        _right = [];
}

3、我们先来进行一次循环，将大于/小于基准值的数的集合，区分开来

function quickSort( _array ){
    //假设我取了数组中间的数作为基准值，得到他的下标, 我们使用~~来获取值为floor时的整数部分，也可以使用Math.floor()来实现
    var _pivot_index = ~~( _array.length / 2 );
    //基准值
    var _pivot = _array.splice(_pivot_index, 1)[0];
    //我们需要两个数组来存放大于小于基准值的集合
    var _left = [] ,
        _right = [];
    for( var i = 0; i < _array.length; i++){
        //这里进行判断，如果大于基准值则放到右侧数组，反之则放到左侧
        _array[i] > _pivot ? _right.push( _array[i] ) : _left.push( _array[i] );
    }
}

4、这样我们区分数组就已经完成了，接下来我们就是要将左右两个数组，分别作为参数传进来，执行相同的操作，那么顺理成章的我们就想到了递归实现, 所以我门增加一个return 递归操作

function quickSort( _array ){
    // 假设我取了数组中间的数作为基准值，得到他的下标, 我们使用~~来获取值为floor时的整数部分，也可以使用Math.floor()来实现
    var _pivot_index = ~~( _array.length / 2 );
    //基准值
    var _pivot = _array.splice(_pivot_index, 1)[0];
    // 我们需要两个数组来存放大于小于基准值的集合
    var _left = [] ,
        _right = [];
    for( var i = 0; i < _array.length; i++){
        // 这里进行判断，如果大于基准值则放到右侧数组，反之则放到左侧
        _array[i] > _pivot ? _right.push( _array[i] ) : _left.push( _array[i] );
    }
    // 因为我们最终要将拆分的数组连接起来，所以这里可以使用concat方法
    // 递归左边的数组 连接基准值 在链接递归右边的数组
    return quickSort( _left ).concat( [ _pivot ], quickSort( _right ) );
}

5、最后我们知道，递归的一个必要点就是退出条件，否则程序会进入死循环，根据上面的核心特点我们知道，此时退出的条件就是当数组的长度小于等于1时，递归退出，那么我们在最开始增加一个if判断

function quickSort( _array ){
     // 这里我们增加一个递归退出条件，当数组长度小于等于1时，退出
    if ( _array.length <= 1 ) return _array;
    // 假设我取了数组中间的数作为基准值，得到他的下标, 我们使用~~来获取值为floor时的整数部分，也可以使用Math.floor()来实现
    var _pivot_index = ~~( _array.length / 2 );
    //基准值
    var _pivot = _array.splice(_pivot_index, 1)[0];
    // 我们需要两个数组来存放大于小于基准值的集合
    var _left = [] ,
        _right = [];
    for( var i = 0; i < _array.length; i++){
        // 这里进行判断，如果大于基准值则放到右侧数组，反之则放到左侧
        _array[i] > _pivot? _right.push( _array[i] ) : _left.push( _array[i] );
    }
    // 因为我们最终要将拆分的数组连接起来，所以这里可以使用concat方法
    // 递归左边的数组 连接基准值 在链接递归右边的数组
    return quickSort( _left ).concat( [ _pivot ], quickSort( _right ) );
}

至此我们就完成了快速排序的基本实现。
当然此方法实现只能作为快速了解快排思路的例子，实际运用中，会带来更大的内存开销等等，等待系列做完，将会逐一分析，并提供更好的思路。

$\color{#34a853}{感谢阅读！}$