🌟个人博客:www.hellocode.top
🏰Java知识导航:Java-Navigate
🔥CSDN:HelloCode.
🌞知乎:HelloCode
🌴掘金:HelloCode
⚡如有问题,欢迎指正,一起学习~~
当谈到高效的排序算法时,归并排序是一个备受推崇的选择。归并排序是一种分治算法,它将一个大问题分解成若干个小问题,然后逐个解决这些小问题,并将它们合并成一个整体的解。
基本思想
这里采用五分钟学算法大佬的图解,十分清晰
- 分解阶段: 将待排序数组分成两个相等或近似相等的子数组,不断将问题规模缩小。
- 解决阶段: 递归地对两个子数组进行排序,直到子数组的长度为1(即已有序)。
- 合并阶段: 将排好序的子数组合并成一个有序的数组,这是归并排序的核心操作。
三个阶段,涉及到递归就比较难理解(个人感觉),最好配合动画好好理解理解。主要就是分解和归并(将大问题分解为小问题,再通过归并过程合并并排序)
代码实现
每次随便写数组挺麻烦的,后续就都使用我写的工具类来生成随机数组了~
归并排序相对难理解一些,主要涉及到分解和归并,将待排序数组一个个拆分,直到拆分为1个1组(无需排序),接下来就是自底向上逐个合并,在合并的同时进行排序操作,最终合并好的就是有序的数组了
/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月15日 19:33*/
public class MergeSort {public static void main(String[] args) {// 生成容量为15的由100以内随机数构成的int数组(用到了自己写的一个工具类)int[] arr = ArrayUtil.randomIntArray(15, 100);System.out.println("原数组:" + Arrays.toString(arr));mergeSort(arr);System.out.println("排序后:" + Arrays.toString(arr));}private static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 数组为空或只有一个元素,无需排序}// 创建临时数组(避免多次创建)int[] temp = new int[arr.length];// 递归入口sort(arr, temp, 0, arr.length - 1);}// 拆分private static void sort(int[] arr, int[] temp, int left, int right) {// 递归出口if (left >= right) {return;}// 记录中间值(左边数组的末尾,+1为右边数组的起始)int mid = left + ((right - left) >> 1);// 开始拆分sort(arr, temp, left, mid);sort(arr, temp, mid + 1, right);// 归并merge(arr, temp, left, mid, right);}// 归并(排序)private static void merge(int[] arr, int[] temp, int left, int mid, int right) {// 记录临时数组索引int p = left;// 左半边起始索引int i = left;// 右半边起始索引int j = mid + 1;// 开始归并// 两边都还有的情况while(i <= mid && j <= right){if(arr[i] <= arr[j]){temp[p++] = arr[i++];}else{temp[p++] = arr[j++];}}// 左边还有剩余的情况(直接加到临时数组末尾)while(i <= mid){temp[p++] = arr[i++];}// 右边还有剩余的情况(直接加到临时数组末尾)while(j <= right){temp[p++] = arr[j++];}// 将临时数组拷贝回原数组for(int k = left; k <= right; k++){arr[k] = temp[k];}}
}
测试:
原数组:[83, 49, 19, 75, 26, 64, 59, 60, 11, 97, 36, 41, 17, 31, 69]
排序后:[11, 17, 19, 26, 31, 36, 41, 49, 59, 60, 64, 69, 75, 83, 97]
生成随机数组的工具类:
/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月13日 20:01*/
public class ArrayUtil {private static final Random RANDOM = new Random();public static int[] randomIntArray(int capacity,int max){// 创建capacity大小的数组(1~max)int[] res = new int[capacity];for(int i = 0; i < capacity; i++){res[i] = RANDOM.nextInt(max) + 1;}return res;}
}
优化
归并排序本身是一个稳定且效率较高的排序算法,但还是有一些优化方法可以进一步提升性能:
- 插入排序优化: 对于小规模子数组,使用插入排序可以提高性能。当子数组长度小于一定阈值时,切换到插入排序可以减少递归调用开销。
- 自底向上归并: 在归并阶段,可以使用自底向上的方法,避免递归调用,从而减少栈空间的使用。
- 优化合并操作: 在合并阶段,如果左子数组的最大元素小于右子数组的最小元素,可以直接跳过合并操作,因为两个子数组已经有序。
总结
优点
- 归并排序稳定且适用于各种数据类型。
- 具有稳定的时间复杂度O(n log n),适用于大规模数据排序。
- 分治思想使其易于理解和实现,同时也为优化提供了空间。
缺点
- 归并排序需要额外的存储空间来存储临时数组,空间复杂度较高。
- 在小规模数据排序时,性能稍逊于快速排序。
复杂度
- 时间复杂度:平均情况、最好情况和最坏情况下的时间复杂度均为O(n log n)。
- 空间复杂度:空间复杂度为O(n),需要额外的存储空间来存储临时数组。
使用场景
- 归并排序适用于需要稳定排序的场景,对性能有一定要求。
- 特别适合用于外部排序,如在磁盘上对大文件进行排序。
通过分治思想,归并排序将排序问题分解为小问题,并通过合并操作将它们逐步解决,从而实现高效且稳定的排序。这使得归并排序成为计算机科学中重要的算法之一。