排序 (四): 归并排序优化

[S-T-D]

• 对小规模数组使用插入排序
  • 实现
• 判断数组是否已经有序
  • 实现

 

对小规模数组使用插入排序

用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%～15%。——《算法（第四版）》

当数据规模较小的时候，用递归来处理并不划算，所以当数据规模较小时，尝试使用插入排序进行排序。

实现

function mergeSort(arr) {
    const aux = new Array(arr.length);
    // 当数组长度为 7 时，切换成插入排序
    const TOGGLE_LENGTH = 7;

    dfs(arr, 0, arr.length - 1, aux);

    function dfs(arr, low, high, aux) {
        // if (low >= high) return;
        // 当子数组 low ~ high 的长度为 TOGGLE_LENGTH 时，切换成插入排序
        if (low + TOGGLE_LENGTH >= high) {
            insertionSort(arr, low, high);
            return;
        }
        const mid = low + Math.floor((high - low) / 2);
        dfs(arr, low, mid, aux);
        dfs(arr, mid + 1, high, aux);
        merge(arr, low, mid, high, aux);
    }

    function merge(arr, low, mid, high, aux) {
        for (let i = low; i <= high; i++) {
            aux[i] = arr[i];
        }
        let j = low;
        let k = mid + 1;
        for (let i = low; i <= high; i++) {
            if (j > mid) {                  
                arr[i] = aux[k++];          
            } else if (k > high) {          
                arr[i] = aux[j++];          
            } else if (aux[j] < aux[k]) {   
                arr[i] = aux[j++];
            } else {
                arr[i] = aux[k++];
            }
        }
    }
}

// 使用之前文章中的插入排序，修改成支持对指定范围进行排序
function insertionSort(arr, low, high) {
    for (let i = low + 1; i <= high; i++) {
        let target = arr[i];
        
        let left = 0, right = i;
        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);
            if (target < arr[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        for (let j = i; j > left; j--) {
            arr[j] = arr[j - 1];
        }
        
        arr[left] = target;
    }
}

 

判断数组是否已经有序

正常情况下，每次将数组折半取得 mid 分成两部分后，最终会调用 merge 将两部分归并回去。

那么如果前后两部分数组已经是有序的，相当于后部分数组的第一个元素大于前部分数组的最后一个元素，也就没有必要再调用 merge 方法，直接返回即可。

对于有序的数组，这样优化后，可以达到线性时间复杂度。

实现

其他部分代码和前面一样，这里只展示修改部分。

function dfs(arr, low, high, aux) {
    // if (low >= high) return;
    // 当子数组 low ~ high 的长度为 TOGGLE_LENGTH 时，切换成插入排序
    if (low + TOGGLE_LENGTH >= high) {
        insertionSort(arr, low, high);
        return;
    }

    const mid = low + Math.floor((high - low) / 2);
    dfs(arr, low, mid, aux);
    dfs(arr, mid + 1, high, aux);

    // 如果已经有序，就不用再 merge
    if (arr[mid] < arr[mid + 1]) return;

    merge(arr, low, mid, high, aux);
}