带你读《图解算法小抄》十四、排序(6)https://developer.aliyun.com/article/1348144?groupCode=tech_library
1)原理
归并排序的基本思想是将待排序的序列不断划分为两个子序列,直到每个子序列只剩下一个元素,然后再将这些子序列两两合并,直到最终得到有序的序列。具体的排序流程如下:
- 步骤1:将待排序序列分成两个子序列,分别进行递归排序;
- 步骤2:将两个已排序的子序列合并成一个有序序列。
function mergeSort(arr) { if (arr.length <= 1) { return arr; } const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); // 递归排序左半部分 const right = mergeSort(arr.slice(mid)); // 递归排序右半部分 return merge(left, right); // 合并左右两个有序子序列} function merge(left, right) { let i = 0; // 左半部分指针 let j = 0; // 右半部分指针 const merged = []; while (i < left.length && j < right.length) { if (left[i] < right[j]) { merged.push(left[i]); // 将较小值放入合并数组 i++; } else { merged.push(right[j]); // 将较小值放入合并数组 j++; } } // 将剩余的元素放入合并数组 return merged.concat(left.slice(i)).concat(right.slice(j)); }
2)优化手段:
尽管归并排序已经是一种高效的排序算法,但我们可以通过一些优化手段进一步提高其性能。下面介绍几种常见的优化策略:
插入排序优化:
对于小规模的子序列,插入排序的时间复杂度较低,因此可以在归并排序的过程中使用插入排序来提高性能。具体做法是,在划分到一定规模后,将子序列采用插入排序算法进行排序。
优化合并过程:
在合并两个有序子序列时,如果发现左边子序列的最大元素小于等于右边子序列的最小元素,那么说明整个序列已经有序,可以直接跳过合并操作,节省时间。
带你读《图解算法小抄》十四、排序(8)https://developer.aliyun.com/article/1348142?groupCode=tech_library