题解 | #排序#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort(arr) {
    // write code here
    // 利用归并排序
    mergeSort(arr, 0, arr.length - 1);
    return arr;
}
// 定义分递归函数
const mergeSort = function (arr, left, right) {
    // 递归终止条件
    if (left === right) return;
    // 中间值,利用位运算符防止数据溢出,更加安全
    let mid = parseInt(left + ((right - left) >> 1));
    // 递归中间值左边部分
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr,left,mid,right);
}
//定义治递归函数
const merge = function(arr,left,mid,right){
    // 定义辅助空数组
    const help = [];
    let i = left;
    let j = mid + 1;
    //定义变量h,用于控制help数组中的元素
    let h = 0;
    while (i <= mid && j <= right) {
        help[h++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    // 将一组比对中的数据都加到help数组中
    while (i <= mid) {
        help[h++] = arr[i++];
    }
    while (j <= right) {
        help[h++] = arr[j++];
    }
    // 将原始数组利用help进行更新
    for (let h = 0; h < help.length; h++) {
        arr[left + h] = help[h];
    }
    return arr;
}
module.exports = {
    MySort: MySort,
};

解题思路

归并排序:时间复杂度为O(n*logn)

该排序算法采用的是分而治之的方法;

(1)分解

将当前数组区间一分为二，求分裂点 mid = (low + high)/2,并递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归分解。分解递归的终结条件是子区间长度为1。

(2)合并

创建辅助数组help,通过比较分组的两个数组中的元素,依次将较小的先入help,将大的后入help;

(3)更新原数组

利用help对原数组进行更新