Quick Sort

Idea

Quick Sort uses divide-and-conquer: pick a pivot, partition into “less than pivot” and “greater than pivot,” then recursively sort both sides.

快速排序演示

61279345108

当前基准 pivot: 6

下一步

Algorithm

1. Choose a pivot (e.g., first element).
2. Partition: left < pivot, right > pivot.
3. Recursively quick-sort left and right.

Pseudo-code:

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

Complexity

• Best/avg: $O(n\log n)$
• Worst: $O(n^2)$ (highly unbalanced partitions)
• Space: $O(\log n)$ (recursion stack)
• Stability: unstable

Exercises

Exercise 1

Run quick sort on $A = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]$; show the first partition result.

参考答案

思路：首元素 6 为基准，划分左右。

步骤：

1. 以 6 为基准，左小右大
2. 一次划分后：[5, 1, 2, 3, 4, 6, 7, 9, 10, 8]

答案：如上，6 左侧更小，右侧更大。

Exercise 2

What are quick sort’s time and space complexities?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n\log n)$（平均），$O(n^2)$（最坏）
2. 空间复杂度 $O(\log n)$

答案：时间 $O(n\log n)$~$O(n^2)$，空间 $O(\log n)$。

PreviousShell SortShell sort basics, algorithm flow, complexity, and practice. NextHeap SortHeap sort fundamentals, algorithm flow, complexity, and practice.