题解 | #排序#

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

解题思路

希尔排序时间复杂度为O(n^3/2)

希尔排序按照规定的某一个增值d（通常为待排数组的length/2）,将待排序数组进行分组，然后对组内元素利用插入排序进行排序；

减少增值d(通常取上次d值的1/2)，继续分组排序；

直到d值减为1后进行一次插入排序即可完成