0
0

快速排序算法(QuickSort)的代码实现

ideawu 发表于 2018年05月10日 19:46 | Hits: 548
Tag: Computer System | IT技术和评论

快速排序算法,也即快排,是递归和分而治之这两种计算机基本思想的应用,再加上其实现逻辑复杂度较好,性能较快,所以快速排序算法非常经典。

快速排序算法经常作为面试算法题。快速排序算法本身并不复杂,其本身的逻辑非常简单,要掌握其思想不是难事,甚至基于其实现代码的形而上学的表面形状背下来也很轻松。但是,如果仅掌握了快速排序的思想以及代码表面形状,就认为自己懂了快速排序,就是没有真正地理解。

快速排序算法作为面试题,一是考查理论结合实践的能力,要求面试者除了知道快速排序算法的实现逻辑和代码形状,还要知道快速排序为什么快,怎么快。二是考查编码细节的能力,考虑的是人经验之外的智商和思维水平。

所以,当我看到一个又一个的前端工程师或者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

Related posts:

  1. 消除JavaScript闭包的一般方法
  2. 写一个对搜索引擎友好的文章SEO分页类
  3. jQuery延时绑定事件(lazy-bind)
  4. JavaScript 设置浏览器标题闪动
  5. 3行代码的分页算法(求起始页和结束页)

原文链接: http://www.ideawu.net/blog/archives/1021.html

0     0

评价列表(0)