type
status
category
date
slug
summary
tags
icon
Last edited time
May 21, 2023 07:57 AM
一、什么是快速排序
快速排序是对冒泡排序对一种改进
- 动图来自菜鸟教程
二、实现方式
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
三、关于快速排序的性能参数
1、空间复杂度
最好:
最坏:
平均:
2、时间复杂度
$O(n^2)$
3、是否稳定
不稳定
4、适用于何类型存储
顺序存储
四、代码实现
1、对于把大的数放到基准数右边，消小的数放到基准数左边
有很多方法
这里使用
two pointers①先将 A[1]存至某个临时变量 temp，并令两个下标 left、right 分别指向序列首尾（如令left=1、right=n）
②只要 right 指向的元素 A[right] 大于 temp，就将 right 不断左移；当某个时候 A[right] ≤temp 时，将元素 A[right]挪到 left 指向的元素 A[left]处。
③只要 left 指向的元素 A[left] 不超过 temp，就将 left 不断右移；当某个时候 A [left]> temp 时，将元素 A[left]挪到 right 指向的元素 A[right]处。
④重复②③，直到 left 与 right 相遇，把 temp（也即原 A [1]) 放到相遇的地方。
代码实现此功能
2、快速排序实现
3、程序实例实现
- 作者:Jimmy Huang
- 链接:https://huangjihao.com/54fa2ed7-4546-434f-96eb-6d44f1f1dc58
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
