网络进行时

在http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html这篇文章中详细描述了快速排序的原理，同时也给出了javascript的实现，其具体代码如下：

function quickSort(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));
}

上述代码也是比较通俗易懂，自己生成一个随机数组测试，排序正确，所以功能上也没有问题。但上述代码还是有一个隐藏的小bug，当对同一个数组调用两次quickSort，发现第二次条用后出来的元素数量会比原始数据少一个。导致这个问题是根源是arr.splice(pivotIndex, 1)[0]，它会把arr中指定位置的元素删掉。其操作是针对该方法的参数，但是同时影响到了传给方法的实际数组，所以结论是javascript中数组参数的是传引用（地址），而非传值。

为了不影响原始数组数据，可以对上述代码进行一个小修改，修改后的代码如下：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr[pivotIndex];
    var left = [];
    var right = [];

    for (var i = 0; i < arr.length; i++) {
        if (i == pivotIndex) {
            continue;
        }

        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat([pivot], quickSort(right));
}

(还没有人进行评分)

Loading...