Javascript和快速排序

2017-07-21 本文已影响195人云峰yf

Javascript和快速排序

这里以递归为例，参考自慕课网刘波波老师的C++版本实现

普通快排

上过大学数据结构课程的人都知道，快速排序的核心就是选定一个哨兵，然后把它作为标准，对数据进行操作，把小的放前面，把大的放后面。然后执行这个过程若干次，就得到了最终的结果。
这个过程，实践了算法中的分治法，即把复杂的模块分成几个简单的模块分而治之，达到事半功倍的效果。
在这里，我推荐一个算法可视化网站：http://zh.visualgo.net/zh/sorting
很多常见的算法可以在上面快速的理解处理过程。
代码如下：

var quickSort = function (arr) {
    __quickSort(arr, 0, arr.length - 1);
    return arr;
}
var __quickSort = function (arr, start, end) {
    if (start > end) {
        return;
    }
    // p是哨兵排序完毕时的位置
    var p = partition(arr, start, end);
    __quickSort(arr, start, p - 1);
    __quickSort(arr, p + 1, end);
    return arr;
}

function partition(arr, start, end) {
    // v是哨兵
    var v = arr[start];
    // j是分界线
    var j = start;
    //从第二个元素开始比较
    for (var i = start + 1; i <= end; i++) {
        if (arr[i] < v) {
            //如果第i个元素比哨兵小，就和右边的大数交换，j就往右移了一位
            [arr[j + 1], arr[i]] = [arr[i], arr[j + 1]];
            // var tmp = arr[start];
            // arr[start] = arr[j];
            // arr[j] = tmp;
            j++;
        }
    }
    //把哨兵放在本应属于他的位置。
    [arr[start], arr[j]] = [arr[j], arr[start]];
    // var tmp = arr[start];
    // arr[start] = arr[j];
    // arr[j] = tmp;
    return j;
}

快排性能测试

怎么知道我们算法的性能呢？我们可以新建一个模块，自动生成测试用例进行测试并且打印出耗时。
test.js

/**
 * 
 * 自定义测试用例
 * @param {any} n 元素个数
 * @param {any} rangeL  范围内最小数，开区间 
 * @param {any} rangeH  范围内最大数，开区间
 * @returns arr 数组
 */
function genTest(n, rangeL, rangeH) {
    if (rangeH < rangeL) {
        return;
    }
    var arr = [];
    for (var i = 0; i < n; i++) {
        arr.push(Math.floor(Math.random() * (rangeH - rangeL)) + rangeL);
    }
    return arr;
}

/**
 * 
 * 耗时计算
 * @param {any} func 要测试的回调函数
 * @param {any} n 元素个数
 * @param {any} [m=n] 最大值，默认为n
 */
function dif(func,n,m=n) {
    console.time(`${func.name}算法耗时`);
    func(genTest(n, 0, m));
    console.timeEnd(`${func.name}算法耗时`);    
}

exports.genTest = genTest;
exports.dif = dif;

这里有一个genTest函数用于产生一个数组，还有一个dif函数用于打印耗时。
然后在之前写的代码里导入,测试一个100万个数据的程序：

var test = require('./test');
...
test.dif(quickSort, 1000000)

解构赋值交换法快排耗时

传统交换变量快排耗时

优化快排

快排常常有两种边界情况需要被考虑：
1.如果待排序的数组是有序的，复杂度会到O(n^2)。
2.数组元素重复个数过多也会造成性能上的损耗。
所以针对这两种情况要进行优化：哨兵要随机选，针对重复的元素还要再加一个指针。

三路快排

这种快排通常被人叫做三路快排，因为它的代码中有三个指针，分别标识着小于哨兵的部分/等于哨兵的部分/大于哨兵的部分。

代码如下：

var test = require('./test');

//更加先进的：三路快排,可能是交换性能消耗大
var quickSortThreeWays = function (arr) {
    var len = arr.length;
    __quickSortThreeWays(arr, 0, len - 1);
    return arr;
}

function __quickSortThreeWays(arr, start, end) {
    if (start > end) {
        return;
    }
    var rand = Math.round(Math.random() * (end - start));
    //partition
    [arr[start], arr[rand + start]] = [arr[rand + start], arr[start]];
    var v = arr[start];

    var lt = start; //arr[start+1...lt]<v
    var gt = end + 1; //arr[gt...end]>v
    var i = start + 1;
    while (i < gt) {
        if (arr[i] < v) {
            [arr[i], arr[lt + 1]] = [arr[lt + 1], arr[i]];
            lt++;
            i++;
        } else if (arr[i] > v) {
            [arr[i], arr[gt - 1]] = [arr[gt - 1], arr[i]];
            gt--;
        } else { //arr[i]==v
            i++;
        }
    }
    [arr[start], arr[lt]] = [arr[lt], arr[start]];
    __quickSortThreeWays(arr, start, lt - 1);
    __quickSortThreeWays(arr, gt, end);
}

可以看到lt——i之间是小于哨兵的、i——gt之间是等于哨兵的，gt——end是大于哨兵的。

//测试三路快排性能
test.dif(quickSortThreeWays, 1000000)

三路快排耗时.png

由于我这里大量使用了解构赋值交换元素，所以也造成了性能上的损耗，再加上js本身不太适合实现底层算法，所以看上去还没有普通快排快，不过在C++写法中是绝对快出一筹的。

特殊情况

大量重复元素

我们把数组限定在0~10的整数范围内，同样生成一百万个。

三路快排重复元素耗时.png

快排重复元素耗时.png

快排解构赋值交换元素耗时.png

test.dif(quickSort, 1000000,100)
test.dif(quickSortThreeWays, 1000000,100)

可以看出这时候三路快排已经比快排快了，而且还是没用解构赋值的快排，如果用解构赋值普通快排会溢出。
至于近乎有序的数组大家可以自己尝试写一个测试用例生成来测试~

其他写法

阮一峰前辈的博客里也有相关的实现，因为用的js原生api比较多，所以我称它为js写法，其实还有很多写法，这里就不一一列举了

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

可以看出，阮前辈使用了splice、concat等众多js本身的api，不过语义上好理解一些，那性能如何呢？我们来看看：

JS快排.png

可以看出，这种写法的性能是比较低的。那两种特殊情况同理。

JS的sort()函数

不过实际上，JS早已帮我们内置好了排序函数，那就是sort()函数。关于sort()函数的实现，chrome是在元素大于10个时使用快排，小于10个的时候使用插入排序，其他的浏览器有用归并排序的，有用选择排序的...
那sort函数的性能如何呢？
我们来看看：

var jsSort = function (arr) {
    return arr.sort((a, b) => { return a - b; });
}

test.dif(jsSort, 1000000);

sort函数耗时.png

这是node环境下的sort，可以看出，性能也不咋地，有兴趣的朋友可以去各个浏览器跑一下看看测试结果~~~
总之，快排虽然在jser们手下不需要手动实现，但是了解其中蕴含的算法思想是极为重要的。

Javascript和快速排序