快速排序
定义与基本思想
快速排序(Quick Sort)是一种分治法思想的高效排序算法。其基本思想是:每次选取一个“基准”元素,将序列分为两部分,左边都比基准小,右边都比基准大,然后递归地对两部分分别排序。
快速排序演示
61279345108
当前基准 pivot: 6
算法描述
- 选取基准元素(如第一个元素)
- 将序列划分为两部分,左边小于基准,右边大于基准
- 分别对左右两部分递归进行快速排序
伪代码如下:
function quickSort(A, low, high):
if low < high:
pivot = partition(A, low, high)
quickSort(A, low, pivot-1)
quickSort(A, pivot+1, high)
function partition(A, low, high):
pivot = A[low]
i = low
j = high
while i < j:
while i < j and A[j] >= pivot:
j--
A[i] = A[j]
while i < j and A[i] <= pivot:
i++
A[j] = A[i]
A[i] = pivot
return i
时间复杂度分析
- 最好/平均情况:
- 最坏情况:(极端不平衡划分)
- 空间复杂度:(递归栈)
- 稳定性:不稳定排序
练习题
练习 1
对数组 进行快速排序,写出第一次划分后的结果。
参考答案
解题思路:第一次以 6 为基准,左右分区。
详细步骤:
- 以 6 为基准,左边比 6 小,右边比 6 大
- 一次划分后:[5, 1, 2, 3, 4, 6, 7, 9, 10, 8](6 在中间)
答案:如上,6 左边都小于 6,右边都大于 6。
练习 2
快速排序的时间复杂度和空间复杂度分别是多少?
参考答案
解题思路:考查复杂度和空间。
详细步骤:
- 时间复杂度 (平均),(最坏)
- 空间复杂度
答案:时间 ~,空间 。