排序

• 冒泡排序

比较两个相邻的数，不过不符合排序规则则交换这两个数的位置（比如升序，前一个比后一个大，则交换位置）。这样一轮下来，最大（或最小）的数就在最后了。在对数组剩下的数重复上述过程，直到排序完成。

function bubbleSort(arr){
    for(var i=0; i<arr.length; i++){
        for(var j=0; j<(arr.length-i); j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1)
            }
        }
    }
    return arr
}

function swap(arr,left,right){
    var temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
bubbleSort(arr)
console.log(arr)

• 选择排序

与冒泡排序类似，也是比较两个相邻的数，但不交换，只是对最小（或最大）的数进行标记，一轮比较完毕后再将最小（或最大）的数放在正确的位置。

function selectSort(arr){
    for(var i=0; i<arr.length; i++){
        var min = i;
        for(var j=i+1; j<arr.length; j++){
            if(arr[j]<arr[min]){
                min = j
            }
        }
        if(i!= min){
            swap(arr,i,min)
        }
    }
}

function swap(arr,left,right){
    var temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
selectSort(arr)
console.log(arr)

• 插入排序

插入排序有点类似打牌时，我们一张一张的拿牌，按顺序放好，新拿的牌再插入到已经排好序的牌里。

function insertSort(arr){
    for(var i=0; i<arr.length; i++){
        var value = arr[i];
        for(j=i-1; j>-1&&arr[j]>value; j--){
            arr[j+1]=arr[j]
        }
        arr[j+1] = value//因为在执行j--后不满足条件才退出for循环，所以这时是arr[j+1]
    }
    return arr
}
var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
insertSort(arr)
console.log(arr)

• 合并排序

其基本思想是将两个已经排序好的数组合并，要比对所有的元素排序来的快。因此，可将数组依次拆开，再不断的两两合并，直至排序完成。

function mergeSort(arr){
    if(arr.length < 2){
        return arr
    }

    var middle = Math.floor(arr.length/2)
    var left = arr.slice(0,middle);
    var right = arr.slice(middle);

    return merge(mergeSort(left),mergeSort(right))
}

function merge(arrLeft,arrRight){
    var result = [];
    var i = 0, j = 0;
    while(i < arrLeft.length && j < arrRight.length){
        if(arrLeft[i] < arrRight[j]){
            result.push(arrLeft[i++])
        }else{
            result.push(arrRight[j++])
        }
    }
    return result.concat(arrLeft.slice(i)).concat(arrRight.slice(j))
}

var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
mergeSort(arr)
console.log(mergeSort(arr))

• 快速排序
  先确定一个支点，然后将小于支点的值放在支点左侧，将大于支点的值放于支点的右侧。对左右两侧不断重复该过程，直至排序完成。

function quickSort(arr,left,right){
    if(arr.length< 2){
        return arr
    }
    if(typeof left != 'number'){
        left = 0
    }
    if(typeof right != 'number'){
        right = arr.length-1
    }
    var index = partition(arr,left,right)
    if(left<index-1){
        quickSort(arr,left,index-1)
    }
    if(index<right){
        quickSort(arr,index,right)
    }
    return arr
}

function partition(arr,left,right){
    var middle = Math.floor((left+right)/2)
    var pivot = arr[middle]
    var i = left, j =right;
    while(i<=j){
        while(arr[i]<pivot){
            i++
        }
        while(arr[j]>pivot){
            j--
        }
        if(i<=j){
            swap(arr,i,j)
            i++
            j--
        }
    }
    return i
}

function swap(arr,left,right){
    var temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}


var arr = [1,5,2,9,2,3,45,21,64,23,7,5]
quickSort(arr)
console.log(arr)

(先这样吧，困死，明天在把桶排和基数排序补上)