摘要：今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法快速排序法平均时间复杂度为。快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。
HTML5学堂-码匠：前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法，它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法
—— 快速排序法 [ 平均时间复杂度为O (n logn) ]。
Tips 1：关于“算法”及“排序”的基础知识，在此前“选择排序法”中已详细讲解，可点击文后的相关文章链接查看，在此不再赘述。
Tips 2：如果无特殊说明，本文的快速排序是从小到大的排序。
快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。
分治法基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解决这些子问题，然后将这些子问题的结果组合成原问题的结果。
基本原理从序列中任选一个数作为“基准”；
所有小于“基准”的数，都挪到“基准”的左边；所有大于等于“基准”的数，都挪到“基准”的右边；
在这次移动结束之后，该“基准”就处于两个序列的中间位置，不再参与后续的排序；
针对“基准”左边和右边的两个子序列，不断重复上述步骤，直到所有子序列只剩下一个数为止。
现有一个序列为 [8, 4, 7, 2, 0, 3, 1]，如下演示快速排序法如何对其进行排序。
实现快速排序的步骤分解 选择“基准”，并将其从原始数组分离先获取基准的索引值，再使用splice数组方法取出基准值。
Tips：该实例中， 基准的索引值 = parseInt（序列长度 / 2）
Tips：splice方法会改变原始数组。例如，arr = [1, 2, 3]; 基准索引值为1，基准值为2，原始数组变为arr = [1, 3];
与“基准”比较大小，并拆分为两个子序列
小于“基准”的数存储于leftArr数组当中，大于等于“基准”的数存储于rightArr数组当中
Tips：当然，也可以将 小于等于“基准”的数存于leftArr，大于“基准”的数存于rightArr
由于要遍历序列，将每一个数与“基准”进行大小比较，所以，需要借助for语句来实现
定义一个函数，形参用于接收数组
function quickSort(arr) { };
实现递归调用遍历子序列，用concat数组方法组合子序列的结果
判断子序列的长度递归调用的过程中，子序列的长度等于1时，则停止递归调用，返回当前数组。
快速排序法完整代码 快速排序法的效率 时间复杂度最坏情况：每一次选取的“基准”都是序列中最小的数/最大的数，这种情况与冒泡排序法类似（每一次只能确定一个数[基准数]的顺序），时间复杂度为O（n^2）
最好情况：每一次选取的“基准”都是序列中最中间的一个数（是中位数，而不是位置上的中间），那么每次都把当前序列划分成了长度相等的两个子序列。这时候，第一次就有n/2、n/2两个子序列，第二次就有n/4、n/4、n/4、n/4四个子序列，依此类推，n个数一共需要logn次才能排序完成（2^x=n，x=logn），然后每次都是n的复杂度，时间复杂度为O（n logn）
最坏情况：需要进行n‐1 次递归调用，其空间复杂度为 O（n）
最好情况：需要logn次递归调用，其空间复杂度为O（logn）
快速排序是一种不稳定排序算法
例如：现有序列为[1, 0, 1, 3]，“基准”数字选择为第二个1
在第一轮比较之后，变成了[0, 1, 1, 3]，左序列为[0]，右序列为[1, 3]（右序列的1是此前的第一个1）
不难发现，原序列的两个1的先后顺序被破坏了，改变了先后顺序，自然就是“不稳定”的排序算法了
在此前的“冒泡排序法”一文当中，我们详细讲解过O是什么，在此就不多说了，直接上图吧
相关文章链接算法之旅 | 选择排序法
算法之旅 | 冒泡排序法
生活艰辛，代码不易，但，不要忘记微笑！
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/91960.html
摘要：由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。 HTML5学堂-码匠：数据快速的计算与排序，与前端页面性能有直接的关系。由于排序的算法有很多，在本次算法系列的分享当中，我们先从简单易上手的选择排序法开始，其它的排序算法会随后陆续跟大家一起分享。 算法的基本概念 算法是什么，它有何作用 为解决一个问题而采取的方...
摘要：学堂码匠本期继续走入算法冒泡排序法。冒泡排序法完整代码冒泡排序法的优化假如序列的数据为使用上面的冒泡排序法进行排序，得到的结果肯定没有问题，但是，待排序的序列是有序的，理论上是无需遍历排序。 HTML5学堂-码匠：本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单，容易上手，稳定性也比较高,算是一种较好理解的算法，也是面试官高频提问的算法之一。 Tips：关于算法及排序的基础知识...
阅读 3257·2023-04-26 02:42
阅读 778·2021-10-09 09:41
阅读 3102·2021-09-06 15:02
阅读 677·2019-08-26 10:45
阅读 469·2019-08-23 15:53
阅读 704·2019-08-22 18:10
阅读 530·2019-08-22 18:01
阅读 3492·2019-08-22 17:34
