快速排序算法, 也即快排, 是递归和分而治之这两种计算机基本思想的应用, 再加上其实现逻辑复杂度较好, 性能较快, 所以快速排序算法非常经典.
快速排序算法经常作为面试算法题. 快速排序算法本身并不复杂, 其本身的逻辑非常简单, 要掌握其思想不是难事, 甚至基于其实现代码的形而上学的表面形状背下来也很轻松. 但是, 如果仅掌握了快速排序的思想以及代码表面形状, 就认为自己懂了快速排序, 就是没有真正地理解.
快速排序算法作为面试题, 一是考查理论结合实践的能力, 要求面试者除了知道快速排序算法的实现逻辑和代码形状, 还要知道快速排序为什么快, 怎么快. 二是考查编码细节的能力, 考虑的是人经验之外的智商和思维水平.
所以, 当我看到一个又一个的前端工程师或者 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 个元素情况). 重合之后, 又可能继续移动导致交叉. 就是这两个情况.
另外, 对于快速排序算法的面试题, 做对做错并不是唯一标准, 如果能完全做对当然是加分, 但即使做错, 也要分情况. 如果暴露了没有计算机素养, 当然要减分. 如果边界条件没考虑全, 应该不会扣分. 更重要的是, 要多问一句, 你怎么把快排算法结合实践?
来源: http://www.tuicool.com/articles/Jbq2e27