快排

#快排

在实际中，快排算法被证明是效率最高的对比算法 (Comparison Sort)。最好情况和 merge sort 一样，达到 Θ(nlgⁿ)。最差是 Θ(n²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 def quicksort(inputs, lo, hi)
  if (lo < hi)
    mi = partition inputs, lo, hi
    quicksort inputs, lo, mi-1
    quicksort inputs, mi+1, hi
  end
end

def partition(inputs, lo, hi)
  key = inputs[hi]
  mi, unsort = lo - 1, lo
  lo.upto(hi-1) do |i|
    if inputs[i] <= key
      mi += 1
      new_value = inputs[i]
      inputs[i] = inputs[mi]
      inputs[mi] = new_value
    end
    unsort += 1
  end
  inputs[hi] = inputs[mi+1]
  inputs[mi+1] = key
  mi + 1
end