排序之快速排序
2022/1/24 23:05:12
本文主要是介绍排序之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 快速排序
- 1 动画
- 2 思想
- 3 实现步骤
- 4 解法
- 写法1
- 写法2
- 5 分析
- 时间复杂度
- 空间复杂度
- 稳定性
- 参考资料:
快速排序
1 动画
2 思想
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。
3 实现步骤
- 选择一个基准元素
target
(一般选择第一个数) - 将比
target
小的元素移动到数组左边,比target
大的元素移动到数组右边 - 分别对
target
左侧和右侧的元素进行快速排序
4 解法
写法1
这种写法浪费大量存储空间,写法简单
- 单独开辟两个存储空间
left
和right来存储每次递归比target小和大的序列 - 每次递归直接返回left、target、right拼接后的数组
function quickSort1(array) { if (array.length < 2) { // 递归出口 return array; } const target = array[0]; // 取数组第一个数为基准元素 const left = []; // 左边数组,存放比 target 小的数 const right = []; // 右边数组,存放不比 target 小的数 for (let i = 1; i < array.length; i++) { // 遍历数组,把元素分到左右两个数组 if (array[i] < target) { left.push(array[i]); } else { right.push(array[i]); } } return quickSort1(left).concat([target], quickSort1(right)); // 递归排序,并把左右两边数组和 target 合并 } // 测试 const array2 = [7, 6, 5, 4, 3, 2, 1]; console.log('quickSort1 ', quickSort1(array2));
写法2
-
定义基准点 target,定义头尾双指针,头指针 left 指向数组最左侧,尾指针 right 指向数组最右侧
-
在头尾指针未相撞之前(即 left < right)
-
尾指针往左移动,遇到比 target 大的就忽略,遇到比 target 小的,就把尾指针的值赋值给头指针
-
头指针往右移动,遇到比 target 小的就忽略,遇到比 target 大的,就把头指针的值赋值给尾指针
-
-
步骤2执行完之后,比 target 大的被分到数组右侧,比 target 小的被分到数组左侧,这时候把 target 插入数组
function quickSort2(array, start, end) { if (start >= end) return; // 递归出口 const target = array[start]; // 定义基准元素 let left = start; // 头指针 left 指向数组最左侧 let right = end; // 尾指针 right 指向数组最右侧 while (left < right) { // 头尾指针未相撞 while (left < right && array[right] >= target) { // array[right] 比 target大(或相等),忽略 right--; } array[left] = array[right]; // 尾指针的值赋值给头指针 while (left < right && array[left] < target) { // array[left] 比 target小,忽略 left++; } array[right] = array[left]; // 头指针的值赋值给尾指针 } array[left] = target; // 把 target 插入数组 // target 左右两边递归排序 quickSort2(array, start, left - 1); quickSort2(array, left + 1, end); return array; } // 测试 const array = [3, 1, 5, 4, 7, 2, 6]; console.log('quickSort2 ', quickSort2(array, 0, array.length-1));
5 分析
时间复杂度
-
最佳情况:
O(nlogn)
-
最差情况:
O(n²)
最差情况比如,
[1, 2, 3, 4, 5]
,每次都拿第一个元素为target
,然后再扫描后面的元素。相当于内外双循环,所以时间复杂度为O(n²)
-
平均情况:
O(nlogn)
空间复杂度
O(logn)
(递归调用消耗)
稳定性
不稳定:快速排序每次交换的元素都有可能不是相邻的,因此它有可能打破原来值为相同的元素之间的顺序。因此,快速排序并不稳定
。
参考资料:
-
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总
-
awesome-coding-js
这篇关于排序之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-04敏捷管理与看板工具:提升研发、设计、电商团队工作效率的利器
- 2025-01-04智慧养老管理工具如何重塑养老生态?
- 2025-01-04如何打造高绩效销售团队:工具与管理方法的结合
- 2025-01-04解决电商团队协作难题,在线文档工具助力高效沟通
- 2025-01-04春节超市管理工具:解锁高效运营与顾客满意度的双重密码
- 2025-01-046种主流销售预测模型:如何根据场景选用最佳方案
- 2025-01-04外贸服务透明化:增强客户信任与合作的最佳实践
- 2025-01-04重新定义电商团队协作:在线文档工具的战略作用
- 2025-01-04Easysearch Java SDK 2.0.x 使用指南(三)
- 2025-01-04百万架构师第八课:设计模式:设计模式容易混淆的几个对比|JavaGuide