常见排序算法

var testArr = [4, 12, 2, 7, 9,8]
    function swap(array, left, right) {
        let temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    /**
     * 冒泡排序
     */
    function bubble(arr) {
        for(let i = 0; i < arr.length; i ++) {
            for(let j = 0; j < arr.length - 1 - i; j ++) {
                if(arr[j] > arr[j+1]) swap(arr, j, j+1)
            }
        }
        return arr;
    }
    /**
     * 插入排序
     */
    function insertion(arr) {
        for(let i = 1; i < arr.length; i ++) {
            for(let j = i - 1; j >= 0; j --) {
                if(arr[j] > arr[j+1]) swap(arr, j, j+1)
            }
        }
        return arr;
    }
    /**
     * 选择排序
     */
    function selection(arr) {
        for(let i = 0; i < arr.length; i ++) {
            let minIndex = i;
            for(let j = i + 1; j < arr.length; j ++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                } 
            }
            swap(arr, i, minIndex);
        }
        return arr;
    }

    /**
     * 归并排序
     */
    function mergeSort(arr) {
        let len = arr.length;
        if(len < 2) {
            return arr;
        }
        let middle = Math.floor(len / 2);
        //拆分成两个子数组
        let left = arr.slice(0, middle);
        let right = arr.slice(middle, len);
        //递归拆分
        let mergeSortLeft = mergeSort(left);
        let mergeSortRight = mergeSort(right);
        //合并
        return merge(mergeSortLeft, mergeSortRight);
    }
    function merge(left, right){
        let result = [];
        while(left.length && right.length) {
            if(left[0] <= right[0]) {
                result.push(left.shift()) //每次都要删除left或者right的第一个元素，将其加入result中
            } else {
                result.push(right.shift())
            }
        }
        //将剩下的元素加上
        while(left.length) {
            result.push(left.shift())
        }
        while(right.length) {
            result.push(right.shift());
        }
        return result;
    }
    /**
     * 快速排序
     */
    function quickSort(arr) {
        if (arr.length <= 1) {//如果数组长度小于等于1无需判断直接返回即可 
            return arr;
        }
    　　var pivotIndex = Math.floor(arr.length / 2);//取基准点 
    　　var pivot = arr.splice(pivotIndex, 1)[0];//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数
    　　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]);//比基准点大的放在右边数组 
    　　　　}
    　　}
            //递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1； 
    　　return quickSort(left).concat([pivot], quickSort(right));

    }
    // console.log(bubble(testArr))
    // console.log(insertion(testArr))
    // console.log(selection(testArr))
    // console.log(mergeSort(testArr))
    console.log(quickSort(testArr))