【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-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++]; // 将右边序列的元素加入临时数组，并移动索引}}// 拷贝左边序列剩余的元素到tempwhile (i <= mid) {temp[tempBeginIndex++] = arr[i++];}// 拷贝右边序列剩余的元素到tempwhile (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)
- 稳定性：稳定
