//定義一個原生的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)