我尝试去写快排，结果。。。

《编程珠玑》第 32 页，提到：“尽管第一个二分查找程序于1946年就已经公布了，但是第一个没有 bug 的二分查找程序在 1962 年才出现。”还说参加课堂测试的专业程序员中， 90% 写的二分查找程序都有 bug 。

真的有那么难吗？我心血来潮，动手写起了快排（不要问为什么不是二分查找）。隐约记得快排的原理如下：

• 在要排序的元素集合中选定一个元素作比较标杆；其他元素分别与此标杆比较，比它小的放在标杆前面，比它大的放在它后面；
• 这样集合就一分为二，对这两部分分别应用步骤一的方法，直到每部分只有一个元素。

简单地写几个测试用例。结果第二个测试就跑不过。为什么知道原理还是写不出正确的程序呢？

聪明的人很快就能调试好出错的程序；记忆力好的，大概见过一次正确的写法后就不会忘。可惜普通人这两样都不占。

那如果普通人的目标是以后能很快地写出快排，应该怎样做呢？我暂时能想到：

• 在原理之上唤醒更多写快排的基本算法思想：一分为二用到分治法；算法会反复用到步骤一，所以有递归；算法不需要额外空间。

• 用少量的待排序元素辅助书写算法。

• 用测试用例保证算法正确性。

根据这个思路，首先要定义使用快排程序的方法：

#!/usr/bin/env ruby
sorted_array = QS.sort(array)

然后定义程序的大致框架：

#!/usr/bin/env ruby

module QS
  extend self
  def sort array
    inner_sort array, 0, array.size - 1
    array
  end
  def inner_sort array, low_pos, hight_pos
  end
  def divide array, low_pos, hight_pos
  end
  def exchange array, i, j
  end

end

inner_sort 跟 divide 为什么要接受两个位置参数？我们没有额外储存空间可用，所以要用上下边界划定排序的作用范围。inner_sort 没有返回值，而 divide 要返回一个位置，确立递归排序的界限。exchange 用来交换元素。

开始写 inner_sort ：

#!/usr/bin/env ruby

module QS
  ...

  def inner_sort array, low_pos, hight_pos
    return if low_pos >= hight_pos
    division = divide array, low_pos, hight_pos
    inner_sort array, low_pos, division - 1
    inner_sort array, division + 1, hight_pos
  end

  ...

end

程序会递归调用 inner_sort 。写递归要注意两点：

• 递归要有终止条件
• 每次递归都要朝着终止条件迈一步

接下来写 divide ：

#!/usr/bin/env ruby

module QS
  ...

  def divide array, low_pos, hight_pos
    target = array[low_pos]
    lo = low_pos
    hi = hight_pos
    while low_pos < hight_pos
      while array[low_pos] <= target && low_pos < hi
        low_pos += 1
      end
      while array[hight_pos] >= target && hight_pos > lo
        hight_pos -= 1
      end
      exchange(array low_pos, hight_pos) if low_pos < hight_pos
    end
    exchange(array, lo, hight_pos)
    hight_pos
  end

  ...

end

divide 方法是快排中最难写、最容易出错的，为免出错：

• 要记住重排元素的技巧 从待排序集合的头部开始找到一个比标杆元素大的，从尾部开始找到一个比标杆元素小的，然后交换两者位置
• 要正确写出比较、查找的上下界限 在遍历元素时要注意数组越界问题和交换元素位置的附加条件： low_pos 必须小于 hight_pos
• 最后要把标杆元素与某个元素交换位置 把标杆元素摆到中间，至于是通过跟 low_pos 还是跟 hight_pos 交换达到这个目的。可以用简单的例子（这个例子是尝试出来的，记不住也没关系）确定，假设待排序的元素集是 [2,1,3]，很容易就能得到要跟 hight_pos 交换。

把 exchange 方法补充好，测试用例也写上，完整的程序是这样的：

#!/usr/bin/env ruby
# usage QS.sort(array) => sorted array

module QS
  extend self
  
  def sort array
    inner_sort array, 0, array.size - 1
    array
  end

  def inner_sort array, low_pos, hight_pos
    return if low_pos >= hight_pos
    division = divide array, low_pos, hight_pos
    inner_sort array, low_pos, division - 1
    inner_sort array, division + 1, hight_pos
  end
  
  def divide array, low_pos, hight_pos
    target = array[low_pos]
    lo = low_pos
    hi = hight_pos
    while low_pos < hight_pos
      while array[low_pos] <= target && low_pos < hi
        low_pos += 1
      end
      while array[hight_pos] >= target && hight_pos > lo
        hight_pos -= 1
      end
      exchange(array low_pos, hight_pos) if low_pos < hight_pos
    end
    exchange(array, lo, hight_pos)
    hight_pos
  end
  
  def exchange array, i, j
    array[i], array[j] = array[j], array[i]
  end

end

if __FILE__ == $0
  require 'test/unit'
  class TestQS < Test::Unit::TestCase
    def test_0
      array = []
      expected = []
      assert_equal expected, QS.sort(array)
    end
    def test_1
      array = [1]
      expected = [1]
      assert_equal expected, QS.sort(array)
    end
    def test_2_0
      array = [1,2]
      expected = [1,2]
      assert_equal expected, QS.sort(array)
    end
    def test_2_1
      array = [2,1]
      expected = [1,2]
      assert_equal expected, QS.sort(array)
    end
    def test_2_2
      array = [1,1]
      expected = [1,1]
      assert_equal expected, QS.sort(array)
    end
    def test_3_0
      array = [1,2,3]
      expected = [1,2,3]
      assert_equal expected, QS.sort(array)
    end
    def test_3_1
      array = [1,3,2]
      expected = [1,2,3]
      assert_equal expected, QS.sort(array)
    end
    def test_3_2
      array = [3,2,1]
      expected = [1,2,3]
      assert_equal expected, QS.sort(array)
    end
    def test_3_3
      array = [2,1,3]
      expected = [1,2,3]
      assert_equal expected, QS.sort(array)
    end
    def test_3_4
      array = [1,1,2]
      expected = [1,1,2]
      assert_equal expected, QS.sort(array)
    end
    def test_3_5
      array = [1,1,1]
      expected = [1,1,1]
      assert_equal expected, QS.sort(array)
    end
    def test_3_6
      array = [1,2,1]
      expected = [1,1,2]
      assert_equal expected, QS.sort(array)
    end
    def test_3_7
      array = [2,1,1]
      expected = [1,1,2]
      assert_equal expected, QS.sort(array)
    end
  end
end