先看一下 Ruby 版本

http://c2.com/cgi/wiki?QuickSortInRuby

Simple/dumb QuickSort in RubyLanguage, choosing the first element as pivot.
 def qsort(list)
  return [] if list.size == 0
  x, *xs = *list
  less, more = xs.partition{|y| y < x}
  qsort(less) + [x] + qsort(more)
 end
Slightly less readable but hey, we save a line :P
 def qs(l)
  return [] if (x,*xs=l).empty?
  less, more = xs.partition{|y| y < x}
  qs(less) + [x] + qs(more)
 end

Slightly more readable, and hey, we save two lines.
 def quicksort a
  (pivot = a.pop) ? quicksort(a.select{|i| i <= pivot}) + [pivot] + quicksort(a.select{|i| i > pivot}) : []
 end

But that, of course, is much too inefficient because it doesn't use partition.

#########

快速排序 (QuickSort)

1、算法思想 快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法 (Divide-and-ConquerMethod)。

（1）分治法的基本思想 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想 设当前待排序的无序区为 R[low..high]，利用分治法可将快速排序的基本思想描述为： ①分解： 在 R[low..high] 中任选一个记录作为基准 (Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间 R[low..pivotpos-1) 和 R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录 (不妨记为 pivot) 的关键字 pivot.key，右边的子区间中所有记录的关键字均大于等于 pivot.key，而基准记录 pivot 则位于正确的位置 (pivotpos) 上，它无须参加后续的排序。 注意： 划分的关键是要求出基准记录所在的位置 pivotpos。划分的结果可以简单地表示为 (注意 pivot=R[pivotpos])： R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys 其中 low≤pivotpos≤high。 ②求解： 通过递归调用快速排序对左、右子区间 R[low..pivotpos-1] 和 R[pivotpos+1..high] 快速排序。 ③组合： 因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

2、快速排序算法 QuickSort void QuickSort(SeqList R, int low, int high) { //对 R[low..high] 快速排序 int pivotpos； //划分后的基准记录的位置 if(low<high){//仅当区间长度大于 1 时才须排序 pivotpos=Partition(R，low，high)； //对 R[low..high] 做划分 QuickSort(R，low，pivotpos-1)； //对左区间递归排序 QuickSort(R，pivotpos+1，high)； //对右区间递归排序 } } //QuickSort

注意： 为排序整个文件，只须调用 QuickSort(R，1，n) 即可完成对 R[l..n] 的排序。

选取自数据结构网站 http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.1.htm