题解 | #排序#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort( arr ) {
    // write code here
    // 计算数组长度
    let len = arr.length
    //利用插入排序，时间复杂度n^2
    for(let i = 1;i< len;i++){
        for(let j = i;j >=1;j--){
            if(arr[j-1]>arr[j]){
                let temp = arr[j-1]
                arr[j-1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}
module.exports = {
    MySort : MySort
};

插入排序时间复杂度最好为O(n)，最坏为O(n^2），具体分两步操作：

（1）假定第一个元素为最大元素，然后从第二个元素开始，如果小于第一个元素，则交换位置；

note:当前元素并非只与前一个元素进行判断以及交换，而是当前元素与之前所有的元素进行比对。小于就进行交换。

（2）一趟插入排序结束，下一趟会从当前元素的下一个元素开始