《算法导论的Java实现》 8 快速排序

Question

本帖最后由 chen09 于 2011-05-25 09:01:24 编辑

Answer 1

如果你只想“知其然”的话，当然不用自己写。
java.util.Collections的sort函数可以满足大部分的要求。我在前面讲分治算法时讲到，java.util.Collections的sort函数实际是调用了java.util.Arrays的sort(List)。
而java.util.Arrays的sort(List)里面主要是调用了mergeSort，也就是讲“分治算法”时，讲到的合并排序。
你说的系统快排也是有的，那就是Arrays的sort(int)，sort(long)等。
不过，那些快速排序更是变种得厉害，没有点基本功，有点难以看懂。最后说一句，虽然有系统快排，不必手写，但是快排的随机化变种里的RANDOMIZED-PARTITION函数还是很用用的，在后面的章节，“以线性期望时间做选择（检索）”中被巧妙的用到了。