//定义一个原生的bubbleSort方法

Array.prototype.bubbleSort = function () {

    for(let i = 0; i < this.length - 1; i += 1) {

        //通过 this.length 次把第一位放到最后,完成排序

        //-i是因为最后的位置是会动态改变的，当完成一次后,最后一位会变成倒数第二位

        for(let j = 0; j < this.length - 1 - i; j += 1) {

            if(this[j] > this[j+1]) {

                const temp = this[j];

                this[j] = this[j+1];

                this[j+1] = temp;

            }

        }

    }

}

const arr = [4,8,0,1,43,53,22,11,0];

arr.bubbleSort();

console.log(arr);

Array.prototype.selectionSort = function() {

    for(let i = 0; i < this.length - 1; ++i) {

        // 假设最小的值是当前的下标

        let indexMin = i;

        //遍历剩余长度找到最小下标

        for(let j = i; j < this.length; ++j) {

            if(this[j] < this[indexMin] ) {

                indexMin = j;

            }

        }

        if(indexMin !== i) {

            //交换当前下标i与最小下标的值，重复this.length次

            const temp = this[i];

            this[i] = this[indexMin];

            this[indexMin] = temp;

        }

    }

};

Array.prototype.insertionSort = function() {

    //从第二个数开始往前比

    for(let i = 1; i<this.length; ++i) {

        //先把值保存起来

        const temp = this[i];

        let j = i;

        while(j > 0) {

            if(this[j-1] > temp) {

                this[j] = this[j-1];

            } else {

                //因为已经是排序过的了，如果比上一位大，那就没必要再跟上上位比较了

                break;

            }

            j -= 1;

        }

        //这里的j有可能是第0位，也有可能是到了一半停止了

        this[j] = temp;

    }

};

const arr = [5,4,3,2,1];

arr.insertionSort();

Array.prototype.mergeSort = function () {

    const rec = (arr) => {

        //如果数组长度为1，说明切完了，可以直接返回

        if (arr.length === 1) { return arr; }

        //切分数组，把每一项都单独切出来

        const mid = Math.floor(arr.length / 2);

        const left = arr.slice(0,mid);

        const right = arr.slice(mid,arr.length);

        //有序的左边数组

        const orderLeft = rec(left);

        //有序的右边数组

        const orderRight = rec(right);

        //定义一个数组来存放顺序数组

        const res = [];

        // 把左右两个有序的合并为一个有序的返回

        while(orderLeft.length || orderRight.length) {

            if(orderLeft.length && orderRight.length) {

                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())

            } else if (orderLeft.length) {

                res.push(orderLeft.shift());

            } else if (orderRight.length) {

                res.push(orderRight.shift());

            }

        }

        return res;

    };

    const res = rec(this);

    //拷贝到数组本身

    res.forEach((n,i) => { this[i] = n; });

}

const arr = [5,4,3,2,1];

arr.mergeSort();

console.log(arr);

Array.prototype.quickSort = function () {

    const rec = (arr) => {

       // 预防数组是空的或者只有一个元素, 当所有元素都大于等于基准值就会产生空的数组

       if(arr.length === 1 || arr.length === 0) { return arr; }

       const left = [];

       const right = [];

       //以第一个元素作为基准值  

       const mid = arr[0];

       //小于基准值的放左边，大于基准值的放右边

       for(let i = 1; i < arr.length; ++i) {

           if(arr[i] < mid) {

               left.push(arr[i]);

           } else {

               right.push(arr[i]);

           }

       }

        //递归调用，最后放回数组   

       return [...rec(left),mid,...rec(right)];

    };

    const res = rec(this);

    res.forEach((n,i) => { this[i] = n; })

}

const arr = [2,3,4,5,3,1];

arr.quickSort();

console.log(arr)