内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

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

2018-05-11 14:28 出处:清屏网 人气: 评论(0

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

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

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

所以,当我看到一个又一个的前端工程师或者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个元素情况)。重合之后,又可能继续移动导致交叉。就是这两个情况。

另外,对于快速排序算法的面试题,做对做错并不是唯一标准,如果能完全做对当然是加分,但即使做错,也要分情况。如果暴露了没有计算机素养,当然要减分。如果边界条件没考虑全,应该不会扣分。更重要的是,要多问一句,你怎么把快排算法结合实践?

分享给小伙伴们:
本文标签: QuickSort快速排序算法

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号