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]