排序算法

1. 冒泡排序

function bubbleSort(arr){
    for(let x=0;x<arr.length;x++){
        for(let y=0;y<arr.length-1;y++){
            if(arr[y]>arr[y+1]){
                [arr[y],arr[y+1]] = [arr[y+1],arr[y]]
            }
        }
    }
    return arr
}

2. 选择排序

function selectionSort(arr){
    for(let x = 0; x<arr.length; x++){
        let minIndex = x
        for(let y = x+1; y<arr.length; y++){
            if(arr[y]<arr[minIndex]){
                minIndex = y
            }
        }
        [arr[x],arr[minIndex]] = [arr[minIndex],arr[x]]
    }
    return arr
}

3. 插入排序

function insertSort(arr){
    for(let x=1; x<arr.length; x++){
        for(let y=x; y>0; y-- ){
            if(arr[y]<arr[y-1]){
                [arr[y-1],arr[y]] = [arr[y],arr[y-1]]
            }else{
                break
            }
        }
    }
    return arr
}

4. 归并排序

function mergeSort(arr){
    if(arr.length<2){
        return arr
    }
    let middle = parseInt(arr.length/2)
    let left = arr.slice(0,middle)
    let right = arr.slice(middle)
    function merge(left,right){
        let result = []
        while(left.length && right.length){
            if(left[0]<=right[0]){
                result.push(left.shift())
            }else{
                result.push(right.shift())
            }
        }
        while(left.length){
            result.push(left.shift())
        }
        while(right.length){
            result.push(right.shift())
        }
        return result
    }
    return merge(mergeSort(left), mergeSort(right))
}

5. 快速排序

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

6. 计数排序

function countingSort(array) {
    var len = array.length,
        B = [],
        C = [],
        min = max = array[0];
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    for (var k = len - 1; k >= 0; k--) {
        B[C[array[k]] - 1] = array[k];
        C[array[k]]--;
    }
    return B;
}