浅析java 归并排序算法
作者:hebedich 时间:2022-01-20 09:59:50
归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的额外空间,时间复杂度为O(nlog(n)),算法不是自适应的,不需要对数据的随机读取。
工作原理:
1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2、设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
运行代码
package com.zc.manythread;
import java.util.Random;
/**
* 归并排序
* @author 偶my耶
*
*/
public class MergeSort {
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
*
* @param data
* 数组对象
* @param left
* 左数组的第一个元素的索引
* @param center
* 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
* @param right
* 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 临时数组
int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int third = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 将临时数组中的内容拷贝回原数组中
// (原left-right范围的内容被复制回原数组)
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
/**
* 产生随机数组
* @param count
* @return
*/
private static int[] createDate(int count) {
int[] data=new int[count];
Random rand = new Random();
boolean[] bool = new boolean[100];
int num = 0;
for (int i = 0; i < count; i++) {
do {
// 如果产生的数相同继续循环
num = rand.nextInt(100);
} while (bool[num]);
bool[num] = true;
data[i]=num;
}
return data;
}
public static void main(String[] args) {
int[] data = createDate(10);
print(data);
mergeSort(data);
System.out.println("排序后的数组:");
print(data);
}
}
运行结果:
标签:java,归并排序算法
0
投稿
猜你喜欢
C语言实现两个矩阵相乘
2023-07-22 12:41:20
Struts2源码分析之ParametersInterceptor拦截器
2023-11-05 00:41:37
java实现简单的图书管理系统
2022-11-25 03:30:11
C#如何给PDF文件添加水印
2021-07-20 14:32:36
C# Winform 分页功能的实现
2023-03-29 06:07:10
spring mvc DispatcherServlet之前端控制器架构详解
2023-07-30 16:53:23
spring boot中使用@Async实现异步调用任务
2023-04-25 13:35:18
Hadoop+HBase+ZooKeeper分布式集群环境搭建步骤
2022-02-13 01:16:33
Spring(AbstractRoutingDataSource)实现动态数据源切换示例
2022-05-23 07:05:08
Maven打包时如何指定启动类
2021-06-16 11:48:00
iOS新浪微博、腾讯微博分享功能实例
2023-06-16 09:15:53
JAVA版排序算法之快速排序示例
2023-04-20 04:37:53
java集合中list的用法代码示例
2023-04-11 23:29:17
java Map接口子类HashMap遍历与LinkedHashMap详解
2021-11-18 04:43:38
Spring Batch批处理框架使用解析
2021-12-24 03:41:19
java字符串遍历的几种常用方法总结
2022-08-19 06:36:41
java为何不能多继承的原因详解
2023-10-12 04:45:00
详解Java实现缓存(LRU,FIFO)
2022-04-24 13:35:26
JDBC实现学生管理系统
2023-01-22 13:22:19
Springboot中如何使用Jackson
2021-07-29 03:27:34