快速排序算法，也即快排，是递归和分而治之这两种计算机基本思想的应用，再加上其实现逻辑复杂度较好，性能较快，所以快速排序算法非常经典。
快速排序算法经常作为面试算法题。快速排序算法本身并不复杂，其本身的逻辑非常简单，要掌握其思想不是难事，甚至基于其实现代码的形而上学的表面形状背下来也很轻松。但是，如果仅掌握了快速排序的思想以及代码表面形状，就认为自己懂了快速排序，就是没有真正地理解。
快速排序算法作为面试题，一是考查理论结合实践的能力，要求面试者除了知道快速排序算法的实现逻辑和代码形状，还要知道快速排序为什么快，怎么快。二是考查编码细节的能力，考虑的是人经验之外的智商和思维水平。
所以，当我看到一个又一个的前端工程师或者PHP程序员看了阮一峰的博客，不明就理地背下代码作为面试题答案，我觉得，这体现了前端工程师和低级的程序员特有的形而上学表面功夫 -- 只能根据代码的形状死记硬背，无法理解编程的本质。
首先，在递归中分配内存就是完全错误的，在可以数组 in-place 排序的情况下，不断分配内存，说明你根本就是完全不懂计算机！如果你辩解说自己懂封装，懂思想这些高级的东西，说明你在胡扯。思想谁都懂，仅懂了思想还是低级程序员。
这里附上快速排序算法的 JavaScript 版本实现：
function compare(a, b){
cmp_count ++;
return a-b;
}
function swap(arr, s, e){
swap_count ++;
var tmp = arr[s];
arr[s] = arr[e];
arr[e] = tmp;
}
function partition(arr, start, end){
var pivot = arr[start];
var s = start;
var e = end;
while(1){
while(compare(arr[s], pivot) < 0){
s ++;
}
while(compare(arr[e], pivot) > 0){
e --;
}
if(s == e){
return s;
}else if(s > e){
return s-1;
}
swap(arr, s, e);
s++;
e--;
}
}
function qsort(arr, start, end){
if(start >= end){
return;
}
var p = partition(arr, start, end);
qsort(arr, start, p);
qsort(arr, p+1, end);
}
很多人仅仅背诵了 qsort() 函数的形状就认为自己懂了。快速排序的重点和难点在 partition() 函数。既然是数组排序，那么仅交换元素不分配内存是必须的，这是基本程序员素养。
这里的实现是 Hoare 的版本，用两个指针分别从数组的前和后相向移动，然后交换比基准数大的和小的数。这没有难点。难点主要在停止条件，这是比较细节的地方，很容易考虑错。这里用了 if-else 来判断最终的分隔的位置，其实对应的是前后两个指针最终重合还是交叉。
交换后两指针可能重合（3个元素的情况），也可能交叉（2个元素情况）。重合之后，又可能继续移动导致交叉。就是这两个情况。
另外，对于快速排序算法的面试题，做对做错并不是唯一标准，如果能完全做对当然是加分，但即使做错，也要分情况。如果暴露了没有计算机素养，当然要减分。如果边界条件没考虑全，应该不会扣分。更重要的是，要多问一句，你怎么把快排算法结合实践？
更多的代码，以及 Lomuto 版本的实现，可看：https://gist.github.com/ideawu/a114679bb8f0a94452d462ae14b7c977
Loading ...