当前位置：首页 > news >正文

排序算法——归并排序

news 2025/1/12 18:15:32

采用分治的思想（将大问题拆除若干个小问题再解决），我们知道单个元素时一定有序，所以我们可以先将数组拆成一个个有序数组（单元素）然后在对这些有序数组合并（使用双指针时间复杂度仅为O(n)），这样就大幅提高了排序的效率。

最重要的是归并排序十分稳定，无论是什么排列的数组我们拆分的时间开销都是O(logn)，合并是O(n)，所以总的时间复杂度都为O(nlogn)，和其它排序算法（桶排序、快排等）相比受待排数组影响小，适合未知数组情况且总量大的情况。

归并排序的讲解见代码部分会结合代码讲解。

public class Main {public static void main(String[] args) {int[] nums = {2,31,5,2,1,6};new Main().mergeSort(nums, new int[nums.length], 0, nums.length - 1);System.out.println(Arrays.toString(nums));}//拆分public void mergeSort(int[] nums, int[] tempArr, int left, int right) {if(right - left <= 0) return;//当没有元素或只有一个元素时不可再分就返回int mid = left + (right - left) / 2;mergeSort(nums, tempArr, left, mid);//分左边的数组mergeSort(nums, tempArr, mid + 1, right);//分右边merge(nums, tempArr, left, right, mid);//合并操作}//合并private void merge(int[] nums, int[] tempArr, int left, int right, int mid) {int i = left, j = mid + 1;//被分出来的两部分数组的首下标int k = left;//我们要操作的tempArr数组的开始位置while(i <= mid && j <= right) {if(nums[i] <= nums[j]) {//左边部分小，把小的数放入tempArrtempArr[k++] = nums[i++];} else {//右边小tempArr[k++] = nums[j++];}}//处理剩余元素while(i <= mid) {tempArr[k++] = nums[i++];}while(j <= right) {tempArr[k++] = nums[j++];}//将tempArr的变化更新到原数组numsfor(int index = left; index <= right; index++) {nums[index] = tempArr[index];}}
}

具体的过程是这样的：

2,31,5,2,1,6

拆分为：
       2,31,5                        2,1,6

   2,31       5               2,1       6                同一颜色代表是从同一集合拆分出的

2 31       5 2   1 6

合并：

合并{2}{31} {2,31} {5} 合并{1}{2} {1,2} {6}

合并{2,5}{31} {2,5,31} 合并{1,2}{6} {1,2,6}

合并{2,5,31}{1,2,6} {1,2,2,5,6,31}