排序算法

周一面sobug 被问了至少两种数组排序。常用的大概就是

Array.sort(function(a,b));
//a<b 是从小到大排序

另外种想写快排，徒手纸上写出来实在太困难了。基础还是太差了
在wiki上找到了各种版本的quickSort

function quickSort(arr,compfunc,left,right){
    if (arguments.length < 2){
        compfunc = quickSort.comp;
    }

    if (arguments.length !== 4){
        left = 0;
        right = arr.length - 1; 
    }

    if (left > right){
        return ;
    }

    var index = quickSort.partition(arr,compfunc,left,right);
    quickSort(arr,compfunc,left,index-1);
    quickSort(arr,compfunc,index+1,right);
};

quickSort.comp = function(a,b){
    return a > b;
};

quickSort.swap = function(arr,lIndex,rIndex){
    var tmp = arr[lIndex];
    arr[lIndex] = arr[rIndex];
    arr[rIndex] = tmp;
};

quickSort.partition = function(arr,compfunc,left,right){
    var index = left;
    var pivot = arr[index];
    quickSort.swap(arr,index,right);

    for(var i = left; i< right ; i++){
        if (compfunc(arr[i],pivot)){
            quickSort.swap(arr,index++,i);
        }
    }
    quickSort.swap(arr,right,index);
    return index;
}

var arr=[1,2,3,4,5,11,3,4,6,999,20,0];
quickSort(arr,function(a,b){return a<b;});
console.log(arr);
//[0, 1, 2, 3, 3, 4, 4, 5, 6, 11, 20, 999]

inserSort

var insertSort = function(arr){
    var key;
    var j;
    var t;
    for (j = 1; j < arr.length; j++) {
        key = arr[j];
        t = j - 1;
        while (t >=0 && arr[t] > key){
            arr[t+1] = arr[t];
            arr[t] = key;
            t--;
        }
    }
    return arr;
}

var arr=[1,2,3,4,5,11,3,4,6,999,20,0];
insertSort(arr);
console.log(arr);
//[0, 1, 2, 3, 3, 4, 4, 5, 6, 11, 20, 999]