数据结构与算法之归并排序
2023-09-14 09:14:23 时间
归并排序概念
归并排序(Merge Sort)是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
动图展示:
- 动图1
- 动图2
代码实现
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
mergeSort(arr, 0, arr.length - 1);
// [5, 6, 3, 1, 8, 7, 2, 4]
// [5, 6, 1, 3, 8, 7, 2, 4]
// [1, 3, 5, 6, 8, 7, 2, 4]
// [1, 3, 5, 6, 7, 8, 2, 4]
// [1, 3, 5, 6, 7, 8, 2, 4]
// [1, 3, 5, 6, 2, 4, 7, 8]
// [1, 2, 3, 4, 5, 6, 7, 8]
}
//归并排序
public static void mergeSort(int[] arr, int low, int high) {
int middle = (high + low) / 2;
//递归结束
if (low < high) {
//处理左边
mergeSort(arr, low, middle);
//处理右边
mergeSort(arr, middle + 1, high);
//归并
merge(arr, low, middle, high);
}
}
//归并操作
//low:开始位置,middle:分割位置,high:结束位置
public static void merge(int[] arr, int low, int middle, int high) {
//用于存储归并后的临时数组
int[] temp = new int[high - low + 1];
//记录第一个数组中需要遍历的下标
int i = low;
//记录第二个数组中需要遍历的下标
int j = middle + 1;
//用于记录在临时数组中存放的下标
int index = 0;
//遍历两个数组取出小的数字,放入临时数组中
while (i <= middle && j <= high) {
//第一个数组的数据更小
if (arr[i] <= arr[j]) {
//把小的数组放入临时数组中
temp[index] = arr[i];
//让下标向后移一位
i++;
} else {
temp[index] = arr[j];
j++;
}
//每存入一个数字后,临时数组下标后移
index++;
}
//上面的循环退出后,把剩余的元素依次填入到temp中,以下两个while只有一个会执行
//前面一个数组有多余数据
while (i <= middle) {
temp[index] = arr[i];
i++;
index++;
}
//后面一个数组有多余数据
while (j <= high) {
temp[index] = arr[j];
j++;
index++;
}
//把临时数组中的数据重新存入原数组
for (int k = 0; k < temp.length; k++) {
arr[k + low] = temp[k];
}
//打印每次排序后的结果
System.out.println(Arrays.toString(arr));
}
}
时间复杂度
最优时间复杂度:O(nlogn)
最坏时间复杂度:O(nlogn)
稳定性:稳定
相关文章
- <leetcode刷题-数组> 【动态规划】【贪心算法】买卖股票的最佳时机
- 算法刷题笔记01:Array
- 【笔记】《游戏编程算法与技巧》1-6
- c++算法之最长递增子序列(LIS)
- 六大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序「建议收藏」
- 快速排序(三种算法实现和非递归实现)
- 基础算法篇——快速排序
- 【数据结构与算法】:交换排序之快速排序(手绘图解+LeetCode原题)
- Go 数据结构和算法篇(六):选择排序
- Go 数据结构和算法篇(七):归并排序
- 排序算法之堆排序
- 检索算法---二分查找
- 希尔排序算法
- java中的排序算法
- java实现选择排序算法详解编程语言
- Java排序算法 – 基数排序详解编程语言
- 多级反馈队列调度算法详解
- 深入了解MySQL常用的排序算法(mysql的排序算法)
- 极速排序Redis实现快速排序(排序算法redis)
- 利用Oracle算法计算数据占比(oracle中计算占比)
- Oracle中的行排序算法改变结果的新思路(oracle中的行排它)
- 基于Redis集群的高效排序算法(redis集群排序)
- Redis集群实现哈希算法的高效方案(redis集群哈希算法)
- asp下几种常用排序算法
- js三种排序算法分享