class Array
  def quick_sort
    return [] if self.empty?
    k = self[0]
    head = 0
    tail = self.length - 1
    while head < tail
      (tail-head).times do
        if self[tail] < k
          self[tail], self[head] = self[head], self[tail]
          break
        end
        tail = tail - 1
      end
      (tail-head).times do
        if self[head] > k
          self[tail], self[head] = self[head], self[tail]
          break
        end
        head = head + 1
      end
    end
    [*(self.slice(0, head).quick_sort), self[head], *(self.slice(head+1, self.length-head-1).quick_sort)]
  end
end

#test
test_len = 20

random_array = []
test_len.times do
  random_array << rand(100)
end

puts "random_array            = [#{random_array.join(‘, ‘)}]"

puts "random_array.quick_sort = [#{random_array.quick_sort.join(‘, ‘)}]"
puts "random_array.sort       = [#{random_array.sort.join(‘, ‘)}]"
puts "quick_sort #{(random_array.quick_sort == random_array.sort) ? "succeed" : ‘failed‘}."

Ruby版快速排序