package com.arithmetic;
import java.util.Random;
/**
* 归并排序
*
一个归并排序的例子:对一个随机点的链表进行排序
分类 排序算法
数据结构 数组
最差时间复杂度 Θ(nlog n)
最优时间复杂度 Θ(n)
平均时间复杂度 Θ(nlog n)
最差空间复杂度 Θ(n)
最佳算法 有时是
*
* @author xugang
*
*/
public class Merge {
//合并已排序的数组
public static void merge( int[] arr , int low , int mid ,int high , int[] temp ){ //int[] a , int[] b
int first = low ;
int first2 = mid+1 ;
int i = 0 ;
for( ; first<=mid && first2<=high; i++ ){
if( arr[first] < arr[first2] ){
temp[i] = arr[first];
first++;
} else{
temp[i] = arr[first2];
first2++;
}
}
while( first<=mid){
temp[i] = arr[first];
first++;i++;
}
while( first2<=high){
temp[i] = arr[first2];
first2++;i++;
}
for (int p = 0; p < i ; p++) {
arr[low+p] = temp[p];
}
}
//递归
public void mergeSort( int[] arr , int first , int last , int[] temp ){
int mid = 0 ;
if( first < last ){
mid = (first+last)/2 ;
mergeSort(arr, first, mid , temp);
mergeSort(arr, mid+1, last , temp);
merge(arr, first, mid, last , temp );
}
}
public static void main(String[] args) {
Random random = new Random();
int size = 100000 ;
int[] r = new int[size];
for (int i = 0; i < r.length; i++) {
r[i] = Math.abs(random.nextInt())%10000000 ;
}
Merge m = new Merge();
int[] temp = new int[r.length];
long l1 = System.currentTimeMillis();
m.mergeSort(r, 0, r.length-1,temp);
long l2 = System.currentTimeMillis();
System.out.println( "消耗=" + (l2 - l1) ) ;
// for (int i = 0; i < r.length; i++) {
// System.out.println(r[i]);
// }
}
}
分享到:
相关推荐
JAVA归并排序算法.pdf
JAVA归并排序
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
java代码-java 归并排序(偶数 子数组已排序)
主要介绍了Java 归并排序算法、堆排序算法实例详解,需要的朋友可以参考下
实现归并排序的一个类
归并排序的链表实现 随机生成实验数据,可以统计算法运行时间
使用Java实现简单的归并排序算法,给大家提供一个参考。
NULL 博文链接:https://128kj.iteye.com/blog/1663631
java归并外排序
归并排序 在排序前,先建好一个长度等于原数组长度的临时数组
利用分治法思想实现归并排序,Java语言描述。
主要介绍了java 归并排序的实例详解的相关资料,需要的朋友可以参考下
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中实现归并排序。此外,文档还包括一个逐步指南,介绍如何在Java中实现归并...
主要简单介绍了java 归并排序算法的工作原理及代码,需要的朋友可以参考下
一年前做的排序动画,归并排序动画一直未完成,今天完成了,与大家共享
java快速排序 归并排序 冒泡排序 选择排序
Java归并排序-附件资源