//  冒泡排序： 让数组中的当前项和后一项进行比较，如果当前项比后一项大，则两项交换位置（让大的靠后）即可
function bubbleSort(arr){
    let temp = null;
    for(let i = 0; i < arr.length - 1; i++){   // 外层循环控制比较的轮数
        for(let j = 0; j < arr.length - 1 - i; j++){
            if(arr[j] > arr[j +1 ]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j +1] = temp;
            }
        }
    }
    return arr;
}

// 选择排序：两个for循环嵌套，外循环记录每次循环开始的位置，内循环查找本次循环内的最小值
function selectionSort(arr){
    let temp = null;
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] > arr[j]){
                temp = arr[i];
                arr[i] = arr[j]
                arr[j] = temp;
            }
        }
    }
    return arr;
}

// 插入排序
function insertionSort(ary){
    let newAry= [];
    newAry.push(ary[0]);

    for(let i=1;i<ary.length;i++){
        let A = ary[i];   // A 新拿到的

        // 和手里的数组相比较（从后向前比较）
        for(let j=newAry.length-1;j>=0;j--){
            let B = newAry[j];
            if (A > B){
                newAry.splice(j+1,0,A);
                break;
            }

            if(j === 0){  //已经比到了第一项 我们把新数据直接插到第一项
                newAry.unshift(A)
            }
        }
    };
    return newAry;
}

// 快速排序
function quickSort(ary){
    if(ary.length<=1){
        return ary;
    }

    // 找到数组的中间项  在原有的数组中把它移除
    let middleIndex = Math.floor(ary.length / 2);
    let middleValue = ary.splice(middleIndex,1)[0];

    // 准备左右两个数组
    let left = [];
    let right = [];
    
    for(let i = 0; i < arr.length; i++){
        let cur = arr[i];
        if(cur < middleValue){
            left.push(cur);
        }else{
            right.push(cur)
        }
    }
    return quickSort(left).concat(middleValue,quickSort(right))
}