SOURCE

/*
console.log("=======1.冒泡排序========")
Array.prototype.bubbleSort = function () {
    for(let i = 0; i < this.length - 1; i += 1) {
        //通过 this.length 次把第一位放到最后,完成排序
        //-i是因为最后的位置是会动态改变的，当完成一次后,最后一位会变成倒数第二位
        
        //次数为n-1轮
        console.log(`当前轮数为${i}`)
        for(let j = 0; j < this.length - 1 - i; j += 1) {
            console.log(`-当前j为${j}`)
            if(this[j] > this[j+1]) { 
                const temp = this[j];
                this[j] = this[j+1];
                this[j+1] = temp;
            }
        }
    }
}

const arr1 = [3,2,1];
arr1.bubbleSort();
console.log(arr1);
*/

/*
console.log("=======2.选择排序========")
Array.prototype.selectionSort = function() { 
    for(let i = 0; i < this.length - 1; ++i) { 
        console.log(`当前轮数为${i}`)
        //也是找n-1轮
        // 假设最小的值是当前的下标
        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;
        }
    }
};


const arr2 = [5,4,3,2,1];
arr2.selectionSort();
console.log(arr2);
*/

/*
console.log("=======3.插入排序========")
Array.prototype.insertionSort = function() { 
    //从第二个数开始往前比
    for(let i = 1; i<this.length; ++i) { 
        console.log(`当前轮数为${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 arr3 = [5,4,3,2,1];
arr3.insertionSort();
console.log(arr3);
*/

console.log("=======4.归并排序========")
Array.prototype.mergeSort = function () { 
    const rec = (arr) => {
        //如果数组长度为1，说明切完了，可以直接返回
        if (arr.length === 1) { console.log(`切完了,arr=${arr}`); return arr; }
        //切分数组，把每一项都单独切出来
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0,mid);
        const right = arr.slice(mid,arr.length);
        console.log(`当前这轮，左分组=${left}，右分组=${right}`)
        //有序的左边数组
        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());
            }
        }
        console.log(`当前res=${res}`)
        return res;
    };
    const res = rec(this);
    //拷贝到数组本身
    res.forEach((n,i) => { this[i] = n; });
}


const arr4 = [5,4,3,2,1];
arr4.mergeSort();
console.log(arr4);