文章标签 ‘js快速排序’

js 快速排序引出参数传递是传值还是传引用

2013年3月27日 没有评论

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));
}

无觅相关文章插件,快速提升流量