排序算法:快速排序的理解与实现

前言

快速排序是一个使用较为广泛的排序算法，它的时间复杂度为O(nlogn)，网络上很多文章讲解的快速排序都不太符合规范，本文以图文的形式详细讲解快速排序，并用JavaScript将其实现，欢迎各位感兴趣的前端开发者阅读本文😁

概念

快速排序算法：首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数” 和 “比基准值大的数”这两个类别。再将其排列成以下形式

接着，分别对基准值两边的数组进行快速排序，直至基准值的左侧只有一个数据，则排序完成。

图解示例

如图所示，我们使用快速排序将其按照从小到大的顺序进行排列。

根据基准值归类数据

• 随机选择一个基准值，此处把4当作基准值
  

  

• 将其他数字和基准值进行比较，小于基准值的往左移，大于基准值的往右移。
  

  

• 首先，比较3与基准值4
  

  

• 3 < 4 ,所以将3往左移
  

  

• 接下来，比较5和基准值4
  

  

• 5 > 4 ，所以将5往右移
  

  

• 重复上述操作，最终结果如图所示。
  

  

• 将基准值4插入序列，这样就完成了第一次归类。基准值左侧的数据都比它小，基准值右侧的数据都比它大。
  

  

分别对归类好的数据进行递归快速排序

如图所示，我们已经根据基准值将数据进行了归类，将数据分为了两部分: 左序列和右序列，我们分别对这两部分数据递归进行快速排序，即可完成整体的排序。

快速排序右序列

• 两边的排序操作与第一步的操作一样，我们对右序列进行排序
  

  

• 随机选择一个基准值，这次选择6
  

  

• 把其余数据分别和分别和基准值6进行比较，小于基准值往左移，大于基准值往右移。
  

  

• 比较数据，移动位置
  

  

• 和前面一样，对左右两边数据进行排序，进而完成整体的排序。此时我们发现基准值的左侧只有5，已经是排序完成状态，不需要任何操作。
  

  

• 此时序列中还剩余：8、9、7，我们将8作为基准值
  

  

• 将基准值与其他数据进行比较后，基准值的两侧都只有一个数据，因此不需要进行任何操作，这样便排序完成了。
  

  

• 回到上一次排序，由于7、8、9完成了排序，所以5、6、7、8、9也完成了排序。
  

  

• 于是，最初选择的基准值4的右边排序完毕
  

  

快速排序左序列

采用同样的方法，选择基准值，比较数据，移动位置。

如图所示，执行完毕后，整体的排序工作也就完成了

用JS实现快速排序

正如图解示例所述，我们想实现快速排序，必须选择一个基准值,然后根据基准值将数据分为两个数组：比基准值小的数组和比基准值大的数组，把比基准值小的数据放进比基准值小的数组里，把大于等于基准值的数据放进比基准值大的数组里。

递归上述操作，直至基准值的左右两侧，任意一侧的数组长度小于2，则结束递归操作。

• 声明一个函数，参数为即将排序的数组
• 计算基准值，由于快速排序的概念中基准值是随机的，所以我们需要使用random函数来生成基准值
• 声明两个数组，分别用于存放基准值划分出来的数据
• 遍历传进来的参数，取出基准值与数组中的其他元素进行大小比较，大于等于基准值的数据放进比基准值大的的数组里，小于基准值的数据放进比基准值小的数组里。
• 分别对基准值划分出来的数据递归执行上述操作，当即将排序的数组长度小于2时，当前数组已经是排好序的，我们终止递归
• 基准值划分出来的两个数组，分别执行完快速排序后，他们数组里的数据已经按照从小到大的顺序进行排列了，我们只需要将其与基准值合并到一起，整体的排序工作也就完成了

接下来，我们将上述思路转化为代码

/**
 * 快速排序:
 * @param arr 需要进行快速排序的数组
 * @returns {*[]|*}
 */
const quickSort = function (arr) {
    if(arr.length < 2) return arr;
    // 随机选择0～arr.length之间选一个基准值
    const pivot = Math.floor(Math.random() * arr.length)
    // 声明两个数组，分别用于存放比基准值小的数据和比基准值大的数据
    let minArr = [];
    let maxArr = [];
    // 根据基准值填充数组
    for(let i = 0; i < arr.length; i++){
        // 大于基准值就放maxArr里
        if(arr[i] >= arr[pivot] && i !== pivot){
            maxArr.push(arr[i]);
        }
        // 小于基准值就放minArr里
        if(arr[i] < arr[pivot] && i !== pivot){
            minArr.push(arr[i])
        }
    }
    // 分别对基准值划分出来的数组递归调用快速排序，然后合并数组
    return [...quickSort(minArr), arr[pivot], ...quickSort(maxArr)];
}

• 测试我们上面实现的快速排序函数

const dataArr = [3,5,8,1,2,9,4,7,6];
console.log(quickSort(dataArr))

本篇文章实现的快速排序完全符合书中对快速排序的定义，但是实际应用时它不是原地排序，会造成过多的内存消耗，且不稳定，排序效率较低。

快速排序的最优实现方式是三路排序，欢迎各位感兴趣的前端开发者阅读我的另一篇文章：排序算法:快速排序优化 => 三路快排的理解与实现

写在最后

• 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
• 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
• 本文首发于掘金，未经许可禁止转载💌