logo

导航菜单

快速排序

定义与基本思想

快速排序(Quick Sort)是一种分治法思想的高效排序算法。其基本思想是:每次选取一个“基准”元素,将序列分为两部分,左边都比基准小,右边都比基准大,然后递归地对两部分分别排序。

快速排序演示

61279345108
当前基准 pivot: 6

算法描述

  1. 选取基准元素(如第一个元素)
  2. 将序列划分为两部分,左边小于基准,右边大于基准
  3. 分别对左右两部分递归进行快速排序

伪代码如下:

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

时间复杂度分析

  • 最好/平均情况:O(nlogn)O(n\log n)
  • 最坏情况:O(n2)O(n^2)(极端不平衡划分)
  • 空间复杂度:O(logn)O(\log n)(递归栈)
  • 稳定性:不稳定排序

练习题

练习 1

对数组 A=[6,1,2,7,9,3,4,5,10,8]A = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 进行快速排序,写出第一次划分后的结果。

参考答案

解题思路:第一次以 6 为基准,左右分区。

详细步骤

  1. 以 6 为基准,左边比 6 小,右边比 6 大
  2. 一次划分后:[5, 1, 2, 3, 4, 6, 7, 9, 10, 8](6 在中间)

答案:如上,6 左边都小于 6,右边都大于 6。

练习 2

快速排序的时间复杂度和空间复杂度分别是多少?

参考答案

解题思路:考查复杂度和空间。

详细步骤

  1. 时间复杂度 O(nlogn)O(n\log n)(平均),O(n2)O(n^2)(最坏)
  2. 空间复杂度 O(logn)O(\log n)

答案:时间 O(nlogn)O(n\log n)~O(n2)O(n^2),空间 O(logn)O(\log n)

搜索