网站首页 > 文章精选 正文
归并排序(Merge Sort)采用的是经典的分治思想,分治法将序列递归地把平均分割成两半,在保持元素顺序的同时将上一步得到的子序列集成到一起。
算法特性
- 稳定性
归并排序是一种稳定的排序算法。
- 时间复杂度
归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。。
- 空间复杂度
归并排序的排序在每一次合并时需要额外的空间,临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。
算法步骤
1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
动画演示
代码实现
Java代码:
Bash
public static int[] mergeSort(int[] sourceArray) {
if (sourceArray == null || sourceArray.length < 2) {
return sourceArray;
}
int length = sourceArray.length;
int[] array = Arrays.copyOf(sourceArray, length);
process(array, 0, length - 1);
return array;
}
public static void process(int[] array, int left, int right) {
if (left >= right) {
return;
}
int mid = left + ((right - left) >> 2);
process(array, left, mid);
process(array, mid + 1, right);
partition(array, left, mid, right);
}
public static void partition(int[] array, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int index = 0;
while (p1 <= mid && p2 <= right) {
help[index++] = array[p1] > array[p2] ? array[p2++] : array[p1++];
}
while (p1 <= mid) {
help[index++] = array[p1++];
}
while (p2 <= right) {
help[index++] = array[p2++];
}
for (int i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
- 上一篇: 经典基础排序算法——归并排序(归并排序例题讲解)
- 下一篇: 归并排序(归并排序代码)
猜你喜欢
- 2025-06-24 算法基础:插入排序 实现原理和应用场景
- 2025-06-24 基础数据结构——八大排序详解(数据结构八种排序算法的思想)
- 2025-06-24 C#程序员必知:如何让你的代码跑得比火箭还快!深度优化实践指南
- 2025-06-24 数据结构与算法之道:解读常数、线性、对数时间复杂度!
- 2025-06-24 排序算法—快速排序(快速排序算法总结)
- 2025-06-24 Python高级排序算法应用(python3 排序算法)
- 2025-06-24 大数据高频面试题之算法题(大数据技术之高频面试题)
- 2025-06-24 用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等
- 2025-06-24 面试常考八股文及算法(一)(八股文的要求)
- 2025-06-24 技术分享:这可能最快的稳定排序算法
- 最近发表
- 标签列表
-
- newcoder (56)
- 字符串的长度是指 (45)
- drawcontours()参数说明 (60)
- unsignedshortint (59)
- postman并发请求 (47)
- python列表删除 (50)
- 左程云什么水平 (56)
- 编程题 (64)
- postgresql默认端口 (66)
- 数据库的概念模型独立于 (48)
- 产生系统死锁的原因可能是由于 (51)
- 数据库中只存放视图的 (62)
- 在vi中退出不保存的命令是 (53)
- 哪个命令可以将普通用户转换成超级用户 (49)
- noscript标签的作用 (48)
- 联合利华网申 (49)
- swagger和postman (46)
- 结构化程序设计主要强调 (53)
- 172.1 (57)
- apipostwebsocket (47)
- 唯品会后台 (61)
- 简历助手 (56)
- offshow (61)
- mysql数据库面试题 (57)
- fmt.println (52)