Quick Sort

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

快速排序的基本步骤如下：

1. 选择基准值（Pivot）：从数列中挑出一个元素，称为“基准”（pivot），这个选择可以是任意的，常见的选择方法包括取首元素、末元素、中元素或随机元素。

2. 分区操作（Partitioning）：重新排列数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归排序：递归地（Recursive）把小于基准值的子数列和大于基准值的子数列排序。

4. 结束条件：当数列的大小减小到不需要排序时（例如，只有一个或零个元素），递归结束。

以下是快速排序算法的伪代码示例：

procedure quickSort(A, lo, hi)
    if lo < hi then
        p := partition(A, lo, hi)
        quickSort(A, lo, p - 1)  // Before p
        quickSort(A, p + 1, hi)   // After p
    end if
end procedure

procedure partition(A, lo, hi)
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop
        do
            i := i + 1
        while A[i] < pivot
        do
            j := j - 1
        while A[j] > pivot
        if i >= j then
            return j // For equal pivot elements
        end if
        swap A[i] with A[j]
    end loop
end procedure

快速排序的性能通常比其他 O(n log n) 算法更好，因为它的内部循环（inner loop）可以在大多数的架构上很有效率地被实现出来。快速排序的平均时间复杂度为 O(n log n)，但在最坏的情况下会退化到 O(n^2)，尤其是当输入数组已经接近排序好的状态时。为了避免这种最坏情况的发生，通常会使用一些策略来选择基准值，例如随机选择基准值，或