MargeSort
2024-10-21 16:09:17
归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使 每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并算法原理:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置。
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
重复步骤3直到某一指针超出序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。
归并算法代码(java):
package
MergeSort;
public
class
MergeSort {
public
static
int
[] mergeSort(
int
[] nums,
int
l,
int
h) {
if
(l == h)
return
new
int
[] { nums[l] };
int
mid = (l + h - l) /
2
;
int
[] leftArr = mergeSort(nums, l, mid);
//左有序数组
int
[] rightArr = mergeSort(nums, mid +
1
, h);
//右有序数组
int
[] newNum =
new
int
[leftArr.length + rightArr.length];
//新有序数组
int
m =
0
, i =
0
, j =
0
;
while
(i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while
(i < leftArr.length)
newNum[m++] = leftArr[i++];
while
(j < rightArr.length)
newNum[m++] = rightArr[j++];
return
newNum;
}
public
static
void
main(String[] args) {
int
[] nums =
new
int
[] {
9
,
8
,
7
,
6
,
5
,
4
,
3
,
2
,
10
};
int
[] newNums = mergeSort(nums,
0
, nums.length -
1
);
for
(
int
x : newNums) {
System.out.println(x);
}
}
}
最新文章
- Android四大组件之actiivity
- h5 摄像头处理 在线视频
- uC/OS-II汇编代码
- PHP 获取图像信息 getimagesize 函数
- ios系统的中arm指令集
- Python实现CART(基尼指数)
- (剑指Offer)面试题22:栈的压入、弹出序列
- C# 根据Word模版生成Word文件
- [CF 351B]Jeff and Furik[归并排序求逆序数]
- Cocos Studio1.5.0.1开发学习笔记(一)
- C# 参数按照ASCII码从小到大排序(字典序)
- JavaScript编程:文档对象模型DOM
- 在gfs2中关闭selinux
- mysql 排序后获得某行的位置
- js动态增加秒数(自动,手动)
- U3D 控件
- [知了堂学习笔记]_MVC设计模式与JavaWEB三层架构
- HTTP,RFC自学心得
- C#面向对象设计的七大原则
- 第四百零一节,Django+Xadmin打造上线标准的在线教育平台—生产环境部署virtualenv虚拟环境安装,与Python虚拟环境批量安装模块