快速排序算法,也即快排,是递归和分而治之这两种计算机基本思想的应用,再加上其实现逻辑复杂度较好,性能较快,所以快速排序算法非常经典。
快速排序算法经常作为面试算法题。快速排序算法本身并不复杂,其本身的逻辑非常简单,要掌握其思想不是难事,甚至基于其实现代码的形而上学的表面形状背下来也很轻松。但是,如果仅掌握了快速排序的思想以及代码表面形状,就认为自己懂了快速排序,就是没有真正地理解。
快速排序算法作为面试题,一是考查理论结合实践的能力,要求面试者除了知道快速排序算法的实现逻辑和代码形状,还要知道快速排序为什么快,怎么快。二是考查编码细节的能力,考虑的是人经验之外的智商和思维水平。
所以,当我看到一个又一个的前端工程师或者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