Quicksort Basics

Quicksort 是一种排序算法，它选择一个元素（枢轴）并重新排序数组，形成两个分区，使得小于枢轴的所有元素都在它之前，而所有元素都在之后。然后将该算法递归地应用于分区，直到对列表进行排序。

**1. Lomuto 分区方案机制：
此方案选择一个 pivot，它通常是数组中的最后一个元素。该算法维护索引以将枢轴放在变量 i 中，并且每次找到小于或等于 pivot 的元素时，此索引都会递增，并且该元素将放置在 pivot 之前。

partition(A, low, high) is
pivot := A[high]
i := low
for j := low to high – 1 do
    if A[j] ≤ pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[high]
return i

快速排序机制：

quicksort(A, low, high) is
if low < high then
    p := partition(A, low, high)
    quicksort(A, low, p – 1)
    quicksort(A, p + 1, high)

快速排序示例： https://i.stack.imgur.com/UWJZY.gif

**2. Hoare 分区方案：
它使用从被分区的数组的末端开始的两个索引，然后朝向彼此移动，直到它们检测到反转：一对元素，一个大于或等于枢轴，一个更小或相等，这是错误的相对于彼此的顺序。然后交换倒置的元素。当索引满足时，算法停止并返回最终索引。Hoare 的方案比 Lomuto 的分区方案更有效，因为它平均减少了三倍的交换，并且即使所有值都相等，它也可以创建高效的分区。

quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p + 1, hi)

划分 ：

partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do:
        i := i + 1
    while A[i] < pivot do
    
    do:
        j := j - 1
    while A[j] > pivot do
    
    if i >= j then
        return j
    
    swap A[i] with A[j]