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]