浅析java 归并排序算法
作者:hebedich 发布时间:2022-01-20 09:59:50
标签:java,归并排序算法
归并排序(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);
}
}
运行结果:
0
投稿
猜你喜欢
- 一、题目描述题目实现:不同的客户端之间需要进行通信,一个客户端与指定的另一客户端进行通信,实现一对一聊天功能。实现一个客户端与指定的另一客户
- 今天做统计时需要对X轴的地区按照地区代码(areaCode)进行排序,由于在构建XMLData使用的map来进行数据统计的,所以在统计过程中
- @ConditionalOnProperty作用及用法在spring boot中有时候需要控制配置类是否生效,可以使用@Conditiona
- 废话不多说了,直接给大家贴代码了,具体代码如下所示:<update id="updateAuditStateAndType&
- ealsticsearch只是后端提供各种api,那么怎么直观的使用它呢?elasticsearch-head将是一款专门针对于elasti
- 使用@Value取值出现的问题在springBoot项目中我们一般会把一些路径或者资源写在配置文件中,方便管理。但是取得时候有可能会出现一些
- 前言前不久遇到一个问题,是公司早期的基础库遇到的,其实很低级,但是还是记录下来。出错点是一个 IO 流的写入bug,我们项目会有一种专有的数
- 因为公司现在换成了nacos,所以自己写了demo学习一下。结果第一步就走不下去。在使用nacos-config读取nacos配置时。发现b
- 本文实例讲述了java实现List中对象排序的方法。分享给大家供大家参考,具体如下:package com.test; import jav
- 一、非配置文件注入1、注入普通字符串直接附在属性名上,在 Bean 初始化时,会赋初始值。@Value("admin")
- 一、简介SpringBoot 最强大的功能就是把我们常用的场景抽取成了一个个starter(场景启动器),我们通过引入SpringBoot
- 一、实验题目二、分析实验要求为:实现一个界面,界面中包含一个文本显示区和两个按钮(存档和读档)读档按钮作用是打开文件并读取内容,将内容显示在
- 程序结构:一、配置 1. 在pom.xml中添加依赖pom.xml文件如下:<?xml version="1.0&
- 一、Socket是什么Socket 的中文翻译过来就是“套接字”。套接字是什么,我们先来看看它的英文含义:插座。Socket 就像一个电话插
- 一般而言,一个项目部署的由:拉取代码->构建->测试->打包->部署等过程组成,如果我们经常需要部署项目,特别是在微
- 针对实例化过程中会做什么的分析,其中主要的是怎么推断出构造方法,怎么进行匹配【1】前言实例化这一步便是在doCreateBean方法的 in
- 一、概述针对八种基本数据类型定义相应的引用类型—包装类(封装类)。二、作用有了类的特点,就可以调用类中的方法,Java才
- 限流器算法目前常用限流器算法为两种:令牌桶算法和漏桶算法,主要区别在于:漏桶算法能够强行限制请求速率,平滑突发请求,而令牌桶算法在限定平均速
- 本文实例讲述了c#图像截取的实现方法。分享给大家供大家参考。具体如下:图像截取的相关代码如下: public Form1()&nb
- 1. 每个编译单元(文件)都只能有一个public类。即每个编译单元都有单一的公共接口,用public类实现。此时,mian()就必须要包含