1、快速排序
var arr = [23,56,345,25,4,235,45,67,25,44,56,6,333,4];

var quickSort = function(arr){
    if(arr.length <= 1){
        return arr;
    }
    var i = Math.floor((arr.length-1)/2);
    var arrLeft = [];
    var arrRight = [];
    //var pivot = arr.splice(i, 1);
    for(var a in arr){
        if(i == a){
            continue;
        }
        if(arr[a] <= arr[i]){
            arrLeft.push(arr[a]);
        }else{
            arrRight.push(arr[a]);
        }
    }
    /*arrLeft = quickSort(arrLeft);
    arrRight = quickSort(arrRight);*/
    return quickSort(arrLeft).concat(arr[i],quickSort(arrRight));
};


//O(n2),O(n2) O(1) 不稳定 冒泡
function bubbleSort(arr){
    var num = 1;
    for(var i=0;i<arr.length;i++){
        for(var j=0;j<arr.length-i-1;j++){
            num +=1;
            if(arr[j]>arr[j+1]){
                var tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
    console.log(num,arr.length);//56 11
    return arr;
}

//选择排序
function selectionSort(arr){
    var num = 1;
    var len = arr.length;
    for(var i=0;i<len-1;i++){
        var numIndex = i;
        for(var j=i+1;j<len;j++){
            num +=1;
            if(arr[j]<arr[numIndex]){
                numIndex = j;
            }
        }
        if(i != numIndex){
             var tmp = arr[numIndex];
             arr[numIndex] = arr[i];
             arr[i] = tmp;
        }

    }
    console.log(num,arr.length);//56 11
    return arr
}

//插入
function insertionSort(arr) {
    var len = arr.length;
    var num = 1;
    for(var i=0;i<len;i++){
        var preIndex = i-1;
        var current = arr[i];
        while(preIndex>=0 && arr[preIndex]>current){
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
            num++;
        }
        arr[preIndex+1] = current;
    }
    console.log(num,arr.length);//24 11
    return arr;
}

/*希尔排序*/
function shellSort(arr) {
    var len =arr.length;
    var num = 1;
    gap = Math.floor(len/2);
    console.log("gap:"+gap);
    while(gap!==0){
        for(var i = gap;i<len;i++){
            var temp = arr[i];
            //console.log("temp:"+temp);
            var j;
            for(j=i-gap;j>=0 && temp<arr[j];j-=gap){
                num += 1;
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
        gap=Math.floor(gap/2);
    }
    console.log(num,arr.length);//12 11
    return arr;
}