排序之快速排序
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
这篇关于排序之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现