快速选择SELECT算法的实现

快速选择SELECT算法的实现

本节，咱们将依据下图所示的步骤，采取中位数的中位数选取枢纽元的方法来实现此SELECT算法，

不过，在实现之前，有个细节我还是必须要提醒你，即上文中2.2节开头处所述，“数组元素索引是从“0...i”开始计数的，所以第k小的元素应该是返回a[i]=a[k-1].即k-1=i。换句话就是说，第k小元素，实际上应该在数组中对应下标为k-1”这句话，我想，你应该明白了：返回数组中第k小的元素，实际上就是返回数组中的元素array[i]，即array[k-1]。ok，最后请看此快速选择SELECT算法的完整代码实现（据我所知，在此之前，从没有人采取中位数的中位数选取枢纽元的方法来实现过这个SELECT算法）：

//copyright@ yansha && July && 飞羽 
//July、updated，2011.05.19.清晨。 
//版权所有，引用必须注明出处：