归并排序Merge Sort
![归并排序.gif](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130630240-1212252730.gif)
1. Merge Sort介绍
Merge Sort是利用归并的思想实现的排序算法,该算法采用经典的分治策略(divide-and-conquer),是一种稳定的排序算法。分治法是将问题分(divide)为一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各个答案“修补”在一起,即分而治之。归并排序对待排序序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终使得所有元素都是有序的。
Merge Sort的基本思想是:递归地将原始序列对半分割,直至不能再分割(即只剩下一个元素时),开始从最小的序列向上合并排序。
- 首先将待排序序列从中间位置(mid = (left + right) / 2)的位置拆开,拆分为两个,并通过递归逐层拆分;
- 分别从左右子序列中选择较小的元素放入到建立的临时空间temp,并移动下标到下一位置;
- 重复上一步骤直至左子序列或右子序列中的某一下标达到末尾;
- 将另一序列剩余的元素依次放入临时空间temp;
- 将临时空间temp的数据依次放入原序列中。
![归并排序思想.png](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130712742-1387050469.png)
1.2 图解说明Merge Sort步骤
举一个例子来具体说明Merge Sort的过程。给出一个无序数列:8,4,5,7,1,3,6,2
使用归并排序将其排列成一个从小到大的有序数列。
![归并排序分阶段.png](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130741005-942805640.png)
- 分解的过程通过递归的方式进行,定义left,mid,right三个变量,分别表示序列的头部,中间和尾部位置。每一次递归都是将原来的mid作为新的right向左递归分解,原来的mid + 1作为新的left向右递归分解,直至left >= right时递归终止。
![归并排序分阶段回溯.png](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130804439-600882951.png)
- 当向左递归left == right时分离出第一个单独的元素(即nums[0] == 8),此时进行第一次回溯,退回到上一轮继续执行向右递归,分离出第二个单独的元素(即nums[1] == 4),此时执行合并操作将nums[0]和nums[1]进行排序并合并。
- “治”的过程需要将两个有序的子序列合并成一个有序序列,也即如上一步中所述,在每一次左右递归结束后将左右两个子序列进行排序并合并,然后回溯到上一轮继续执行递归分解。此过程中需要定义一个临时空间,合并的结果先放入临时空间,再赋值给原nums序列的相应位置。下图为了方便仅演示最后一次合并的过程。
![归并排序治阶段.png](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130837915-1305555147.png)
![归并排序治阶段2.png](/i/l/?n=23&i=blog/3116926/202304/3116926-20230416130857760-193317749.png)
1.3 代码实现
package com.algorithm;
import java.util.Arrays;
/**
* @author SnkrGao
* @create 2023-04-15 20:10
*/
public class MergeSort {
public static void main(String[] args) {
int[] nums = {6,5,3,1,8,7,2,4};
System.out.println("排序前的数组为:");
System.out.println(Arrays.toString(nums));
mergeSort(nums, 0, nums.length - 1);
System.out.println("排序后的数组为:");
System.out.println(Arrays.toString(nums));
}
public static void mergeSort(int[] nums, int left, int right) {
if (left >= right) { // 递归终止条件
return;
}
int mid = (left + right) / 2; // 定义中间位置index
mergeSort(nums, left, mid); // 向左递归分解
mergeSort(nums, mid + 1, right); // 向右递归分解
// 每一次左右递归结束后将左右两个子序列合并
merge(nums, left, mid, right);
}
public static void merge(int[] nums, int left, int mid, int right) {
// 定义一个临时空间,用于存放合并的结果
// 注意temp的长度并非固定,而是根据每次要合并的序列长度决定
int[] temp = new int[right - left + 1];
int tempLeft = left; // 用于在左子序列移动的左指针
int tempMid = mid + 1; // 用于在右子序列移动的右指针
int index = 0; // temp的当前位置索引
// 从两个子序列中选择最小的放入temp,并移动相应的指针,直至有一个序列处理完毕全部放入temp中
while (tempLeft <= mid && tempMid <= right) {
temp[index++] = nums[tempLeft] <= nums[tempMid] ? nums[tempLeft++] :nums[tempMid++];
}
// 若左子序列仍有剩余,全部依次放入temp
while (tempLeft <= mid) {
temp[index++] = nums[tempLeft++];
}
// 若右子序列仍有剩余,全部依次放入temp
while (tempMid <= right) {
temp[index++] = nums[tempMid++];
}
// 将temp赋值给原序列nums的相应位置
for (int i = 0; i < temp.length; i++) {
nums[i + left] = temp[i];
}
}
}
1.4 Merge Sort时间复杂度分析
Merge Sort每次都将待排序序列折半分组,其时间复杂度可以用递归树来求解,共需要\(logn\)轮。
最坏情况时间复杂度:O(\(nlogn\))
平均时间复杂度:O(\(nlogn\))
标签:归并,递归,nums,int,算法,序列,排序,left From: https://www.cnblogs.com/SnkrGao/p/17323139.html