数据结构-归并排序笔记
【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-CSDN博客
看这个学思路
一 归并排序介绍:
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
二 实现思路
-
分解（Divide）：
- 将待排序的序列分割成若干个子序列，这些子序列可以是顺序的，也可以是随机的。
- 分解的标准通常是按照序列的中间位置或者某个特定的划分点来划分序列。
-
解决（Conquer）：
- 递归地对每个子序列进行排序。
- 递归的基本情况是当子序列足够小，可以直接排序或者已经有序，不需要进一步分解。
-
合并（Combine）：
- 将排序好的子序列合并成一个有序的完整序列。
- 合并操作的复杂度通常取决于具体的算法，例如归并排序中的合并操作需要将两个有序序列合并成一个有序序列。
三 代码实现
实现1
public class Main {
public static void main(String[] args) {
int[] arr = {11, 44, 23, 67, 88, 65, 34, 48, 9, 12}; // 待排序数组
int[] tmp = new int[arr.length]; // 新建一个临时数组，用于在归并过程中存放元素
mergeSort(arr, 0, arr.length - 1, tmp); // 调用归并排序方法，传入数组、起始索引、结束索引和临时数组
// 输出排序后的数组
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// 归并排序方法，采用递归实现
private static void mergeSort(int[] arr, int left, int right, int[] tmp) {
if (left < right) { // 如果左索引小于右索引，说明当前区间内有多个元素，需要排序
int mid = (left + right) / 2; // 计算中间索引，将当前区间分为两半
// 对左边序列进行归并排序
mergeSort(arr, left, mid, tmp);
// 对右边序列进行归并排序
mergeSort(arr, mid + 1, right, tmp);
// 合并两个有序序列
merge(arr, left, mid, right, tmp);
}
}
// 归并方法，用于合并两个有序序列
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int tempBeginIndex = 0; // 临时数组的起始索引
int i = left; // 左边序列的起始索引
int j = mid + 1; // 右边序列的起始索引
// 合并两个有序序列到临时数组temp中
while (i <= mid && j <= right) { // 当左右序列都还有元素时
if (arr[i] <= arr[j]) { // 如果左边序列的元素小于等于右边序列的元素
temp[tempBeginIndex++] = arr[i++]; // 将左边序列的元素加入临时数组，并移动索引
} else {
temp[tempBeginIndex++] = arr[j++]; // 将右边序列的元素加入临时数组，并移动索引
}
}
// 拷贝左边序列剩余的元素到temp
while (i <= mid) {
temp[tempBeginIndex++] = arr[i++];
}
// 拷贝右边序列剩余的元素到temp
while (j <= right) {
temp[tempBeginIndex++] = arr[j++];
}
// 将temp中的元素拷贝回原数组arr，完成合并
for (int k = 0; k < tempBeginIndex; k++) {
arr[left + k] = temp[k];
}
}
}实现2
主要就是合并的时候有区别。可以确保每次合并只用一次。
public class Main {
public static void main(String[] args) {
// 初始化一个整型数组，包含一些无序的元素
int[] arr = {1, 3, 2, 3, 1};
// 创建一个临时数组，用于在归并排序过程中临时存放数据
int[] tmp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, tmp);
// 打印排序后的数组
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// 归并排序的主要方法，递归地将数组分为两半，直到无法再分
private static void mergeSort(int[] arr, int left, int right, int[] tmp) {
// 如果左边界小于右边界，说明还有元素可以继续划分
if (left < right) {
// 计算中间索引，将数组分为两半
int mid = (left + right) / 2;
// 递归地对左半部分进行归并排序
mergeSort(arr, left, mid, tmp);
// 递归地对右半部分进行归并排序
mergeSort(arr, mid + 1, right, tmp);
// 合并两个已排序的半部分
Merge(arr, left, mid, right, tmp);
}
}
// 合并两个有序数组的方法
public static void Merge(int record[], int left, int mid, int right, int temp[]) {
// 初始化两个指针，分别指向左右两个子数组的开始位置
int i = left;
int j = mid + 1;
// 将原数组中的元素复制到临时数组中，以便在合并过程中使用
for (int k = left; k <= right; k++) {
temp[k] = record[k];
}
// 合并过程，将两个有序子数组合并到原数组中
for (int k = left; k <= right; k++) {
// 如果左指针已经到达子数组的末尾，将右子数组的元素拷贝到原数组
if (i == mid + 1) {
record[k] = temp[j++];
}
// 如果右指针已经到达子数组的末尾，或者左子数组的当前元素小于等于右子数组的当前元素
// 则将左子数组的元素拷贝到原数组
else if (j == right + 1 || temp[i] <= temp[j]) {
record[k] = temp[i++];
}
// 如果右子数组的当前元素小于左子数组的当前元素，则将右子数组的元素拷贝到原数组
else {
record[k] = temp[j++];
}
}
}
}四 总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定