归并排序 Merge sort 转

fokYaland

public   class   MergeSort {
public   static   final   int   CUTOFF   = 11;

public   static   void   main(String[] args) {
//   TODO   Auto-generated method stub
int [] a;
int   n = 300;
// 生产随机数组
a =   new   int [n];
Random rand =   new   Random();
for   (   int   i = 0; i < a.   length ; i++) {
a[i] = rand.nextInt(n);
}
//a = new int [] {33,10,80};
println(a);

long   s = System. nanoTime();
int [] b = mergeSort(a);
long   dur = System. nanoTime() - s;
println(b);
System.   out .println(dur);

}

public   static   int [] mergeSort(   int [] a) {
int [] tmp =   new   int [a.   length ];
split(a, tmp, 0, a. length -1);
return   tmp;
}

public   static   void   split( int [] a,   int [] tmp,   int   left,   int   right) {
//System.out.println(left+","+right);
if   (left < right) {
int   center = (left + right) / 2;
//System.out.println(center);
split(a, tmp, left, center);
split(a, tmp, center + 1, right);
merge(a,tmp,left,center+1,right);
}
//System.out.println("返回");
}
public   static   void   merge( int [] a, int [] tmp, int   lPos, int   rPos, int   rEnd){
//System.out.println("merge:"+lPos+","+rPos+","+rEnd);
int   lEnd = rPos -1;
int   tPos = lPos;
int   leftTmp = lPos;
while (lPos <= lEnd && rPos <= rEnd){
if (a[lPos] <= a[rPos]){
tmp[tPos++] = a[lPos++];
}   else {
tmp[tPos++] = a[rPos++];
}
}

while (lPos <= lEnd){
tmp[tPos++] = a[lPos++];
}

while (rPos <= rEnd){
tmp[tPos++] = a[rPos++];
}
// copy the tmpArr back cause we need to change the arr array items.
for   ( ; rEnd >= leftTmp; rEnd-- )
a[rEnd] = tmp[rEnd];

}

public   static   void   println( int [] a) {
System.   out .print(   "[" );
for   (   int   i = 0; i < a.   length ; i++) {
System.   out .print(a[i]);
if   (i != a.   length   - 1)
System.   out .print(   "," );
}
System.   out .println(   "]" );
}

}

fokYaland

stl-stable_sort源码学习笔记

huangjunkun
2011/11/07
0
0
MIT Introduction to Algorithms 学习笔记(四)

lecture 3 Insertion Sort, Merge Sort 1.(插入排序)Insertion sort def InsertSort(L): if(len(L) == 0 or len(L) == 1): return L tmp = 0 for i in range(1,len(L)): for j in range(i,0,......

hyaicc
2015/12/21
31
0

mjrao
2012/03/23
0
0
C++ 归并排序 求高手解答

hjhomw
2015/07/14
131
2

brianway
2016/05/08
133
2

Erc20Tokens数据集包含超过1000种主流的以太坊ERC20代币的描述数据清单和图标，可用于钱包等区块链应用的开发，支持使用Java、Python、Php、NodeJs、C#等各种开发语言查询主流ERC20代币的相关...

32分钟前
1
0
micro微服务 基础组件的组织方式

micro微服务 基础组件的组织方式 简介 micro是go语言实现的一个微服务框架，该框架自身实现了为服务常见的几大要素，网关，代理，注册中心，消息传递，也支持可插拔扩展。本本通过micro中的一...

59分钟前
4
0

ZeroBit

3
0
The /usr/local/mysql/data directory is not owned by the 'mysql' to '_mysql' user

20190720 经过前两天折腾环境，重装了 apache 和 mysql 之后，今天调试程序是突然发现，本机的 mysql 起不来了！ 在启动面板上，显示有这样一行小字 (抱歉！光顾着解决问题，没有记录下来图片...

wwzzhh166

4
0