quickSort

快速排序 - 经典的分治排序算法,平均性能最佳。

输入数组

待排序数组 (用逗号分隔)

执行过程

步骤 1 / 29

开始快速排序

0

38

1

27

2

43

3

3

4

9

5

82

6

10

速度:慢速正常快速超快

基准值

比较中

交换中

已排序

算法说明

快速排序采用分治法,选择基准元素将数组分为两部分递归排序。使用播放控制器可以逐步观察排序过程！平均时间O(n log n)。

函数签名

function quickSort(arr: number[]): number[]
function quickSort3Way(arr: number[]): number[]
function quickSortRandomized(arr: number[]): number[]

参数

参数名	类型	必填	说明
arr	number[]	是	待排序数组

返回值

类型	说明
number[]	排序后的数组

工作原理

1. 选择基准: 选择一个元素作为pivot
2. 分区: 将小于pivot的放左边,大于的放右边
3. 递归排序: 分别对左右两部分递归快排
4. 终止条件: left >= right时停止

三路快排: 将数组分为 < pivot, = pivot, > pivot 三部分,处理大量重复元素更高效

随机化: 随机选择基准,避免最坏情况O(n²)

时间复杂度:

• 平均: O(n log n)
• 最坏: O(n²)

空间复杂度: O(log n)
特点: 不稳定排序,原地排序