亚洲精品无码永久中文字幕,亚洲精品国产成人99久久,久久久亚洲欧洲日产国码农村

排序算法java版，速度排行：冒泡排序、簡(jiǎn)單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序

先推薦一篇關(guān)于排序算法的文章：http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

本文思路部分來(lái)源于上篇文章，但測(cè)得的結(jié)果似乎不大相同，不知是因?yàn)閖ava的緣故還是因?yàn)槲宜惴ǖ木壒剩瑲g迎拍磚。

復(fù)習(xí)排序，順便比下各種算法的速度，榜單如下：

1、冒泡排序

2、簡(jiǎn)單選擇排序

3、直接插入排序

4、折半插入排序

5、希爾排序

6、堆排序

7、歸并排序

8、快速排序

當(dāng)然這是慢速排行，哈哈~~

直接上圖：?jiǎn)挝缓撩?/p>

數(shù)量	冒泡排序	簡(jiǎn)單選擇排序	直接插入排序	折半插入排序	希爾排序	堆排序	歸并排序	快速排序
10000個(gè)	1578	1250	672	250	0	15	16	0
15000個(gè)	3453	2765	1563	531	16	15	16	0
20000個(gè)	6140	4547	2453	828	16	16	15	16
25000個(gè)	10079	7171	3969	1313	31	16	15	16
30000個(gè)	14641	10313	5578	1906	31	31	16	31
35000個(gè)	20141	14328	7890	2563	31	31	32	15
40000個(gè)	25766	18359	10094	3422	47	31	31	32
45000個(gè)	32469	24063	13062	4359	47	47	31	47

由于"希爾排序","堆排序","歸并排序","快速排序"太快，以至于在上圖幾乎是條直線，故有了下面轉(zhuǎn)為他們準(zhǔn)備的加強(qiáng)版

數(shù)量	希爾排序	堆排序	歸并排序	快速排序
100000個(gè)	172	140	110	93
200000個(gè)	469	406	235	234
300000個(gè)	812	703	422	375
400000個(gè)	1125	1031	516	531
500000個(gè)	1406	1282	719	656
600000個(gè)	1828	1703	860	859
700000個(gè)	2531	2063	1000	968
800000個(gè)	2735	2453	1140	1188
900000個(gè)	3047	2843	1391	1266
1000000個(gè)	3375	3187	1516	1422
1100000個(gè)	3922	3500	1625	1609
1200000個(gè)	4421	3954	1969	1812
1300000個(gè)	4797	4422	2000	1953
1400000個(gè)	5391	4797	2547	2094
1500000個(gè)	5437	5219	2625	2328
1600000個(gè)	6203	5546	2469	2485
1700000個(gè)	6532	5953	2844	2672
1800000個(gè)	7125	6421	2984	2844

補(bǔ)上代碼：

Java代碼

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 插入排序:直接插入排序、折半插入排序和系爾排序
* 交換排序:冒泡排序和快速排序
* 選擇排序:簡(jiǎn)單選擇排序和堆排序
* 歸并排序:歸并排序
*
* 基本思想
* 插入排序:將第N個(gè)記錄插入到前面(N-1)個(gè)有序的記錄當(dāng)中。
* 交換排序:按照某種順序比較兩個(gè)記錄的關(guān)鍵字大小，然后根據(jù)需要交換兩個(gè)記錄的位置。
* 選擇排序:根據(jù)某種方法選擇一個(gè)關(guān)鍵字最大的記錄或者關(guān)鍵字最小的記錄，放到適當(dāng)?shù)奈恢谩?
*
* 排序方法比較
* 排序方法平均時(shí)間最壞時(shí)間輔助存儲(chǔ)
* 直接插入排序 O(N2) O(N2) O(1)
* 起泡排序 O(N2) O(N2) O(1)
* 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
* 簡(jiǎn)單選擇排序 O(N2) O(N2) O(1)
* 堆排序 O(Nlog2N) O(Nlog2N) O(1)
* 歸并排序 O(Nlog2N) O(Nlog2N) O(n)
* 基數(shù)排序 O(d(n+radix)) O(d(n+radix)) O(radix)
*
*
*
* @author Administrator
*
*/
public class SortTest {
public static void main(String[] args)throws Exception {
//測(cè)試排序是否正確
//String[] testErr=new String[]{"冒泡排序","簡(jiǎn)單選擇排序","直接插入排序","折半插入排序","系爾排序","堆排序","歸并排序","快速排序"};
//new SortTest().testErr(testErr);
//排序1（全部）
String[] strs=new String[]{"冒泡排序","簡(jiǎn)單選擇排序","直接插入排序","折半插入排序","希爾排序","堆排序","歸并排序","快速排序"};
new SortTest().test(strs,10000,50000,5000);
//排序2（加強(qiáng)）
String[] strs2=new String[]{"希爾排序","堆排序","歸并排序","快速排序"};
new SortTest().test(strs2,100000,1900000,100000);
}
private void testErr(String[] strings) throws Exception{
//System.out.println(Arrays.toString(old));
System.out.println(Arrays.toString(strings));
Number[] old=getRundom(50);
Integer[] oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};
old=oo;
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long begin=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long end=System.currentTimeMillis();
System.out.println(s+":"+(end-begin)+"\t");
System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
private void test(String[] strings,long begin,long end,long step) throws Exception{
System.out.print("數(shù)量\t");
for(String str:strings){
System.out.print(str+"\t");
}
System.out.println();
for(long i=begin;i<end;i=i+step){
System.out.print(i+"個(gè)\t");
Number[] old=getRundom(i);
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long beginTime=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long endTime=System.currentTimeMillis();
System.out.print((endTime-beginTime)+"\t");
//System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
}
private static Integer[] getRundom(long num) {
List<Integer> list=new ArrayList<Integer>();
for(long i=0;i<num;i++){
int k;
if(Math.random()>0.5){
k=(int)(Math.random()*Integer.MAX_VALUE);
}else{
k=(int)(Math.random()*Integer.MIN_VALUE);
}
list.add(k);
}
return list.toArray(new Integer[list.size()]);
}
/**
* 插入排序————直接插入排序
* @param data
*/
public static void 直接插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int j=i-1;
while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){
data[j+1]=data[j];
j--;
}
data[j+1]=tmp;
}
}
/**
* 插入排序————折半插入排序
* @param data
*/
public static void 折半插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int smallpoint=0;
int bigpoint=i-1;
while(bigpoint>=smallpoint){
int mid=(smallpoint+bigpoint)/2;
if(tmp.doubleValue()>data[mid].doubleValue()){
smallpoint=mid+1;
}else{
bigpoint=mid-1;
}
}
for(int j=i;j>smallpoint;j--){
data[j]=data[j-1];
}
data[bigpoint+1]=tmp;
}
}
/**
* 插入排序————希爾排序
* @param data
*/
public static void 希爾排序(Number[] data)
{
int span=data.length/7;
if(span==0)span=1;
while(span>=1){
for(int i=0;i<span;i++){
for(int j=i;j<data.length;j=j+span){
//組內(nèi)直接插入排序
int p = j-span;
Number temp = data[j];
while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
data[p+span] = data[p];
p -=span;
}
data[p + span] = temp;
}
}
span=span/2;
}
}
/**
* 交換排序————冒泡排序
*
* @param data
*/
public static void 冒泡排序(Number[] data)
{
for (int i = 0; i < data.length; i++) {
//將相鄰兩個(gè)數(shù)進(jìn)行比較，較大的數(shù)往后冒泡
for (int j = 0; j < data.length - i-1; j++) {
if (data[j].doubleValue()> data[j + 1].doubleValue()) {
//交換相鄰兩個(gè)數(shù)
swap(data, j, j + 1);
}
}
}
}
/**
* 交換排序————快速排序
* @param data
*/
public static void 快速排序(Number[] data)
{
QuickSort(data,0,data.length-1);
}
private static void QuickSort(Number[] data, int begin, int end) {
// System.out.println(begin+":"+end);
if(begin<end){
//取中點(diǎn)
int mid=(begin+end)/2;
if(data[end].doubleValue()<data[begin].doubleValue()){
swap(data, end, begin);
}
if(data[end].doubleValue()<data[mid].doubleValue()){
swap(data, end, mid);
}
if(data[mid].doubleValue()<data[begin].doubleValue()){
swap(data, mid, begin);
}
swap(data, mid, begin);
// System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );
int min=begin+1;
int big=end;
while(true){
while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}
while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}
if(min>=big){
break;
}
swap(data, min, big);
}
if(data[begin].doubleValue()>data[min].doubleValue()){
swap(data, begin, min);
}
if(min>1)
QuickSort(data,begin,min-1);
//if(min<end)
QuickSort(data,min,end);
}
}
/**
* 選擇排序————簡(jiǎn)單選擇排序
* @param data
*/
public static void 簡(jiǎn)單選擇排序(Number[] data)
{
for (int i = 0; i < data.length-1; i++) {
int smallPoint=i;
for (int j = i+1; j < data.length; j++) {
if (data[smallPoint].doubleValue()> data[j].doubleValue()) {
smallPoint=j;
}
}
swap(data, i, smallPoint);
}
}
/**
* 選擇排序————堆排序
* @param data
*/
public static void 堆排序(Number[] data)
{
int n = data.length;
for(int i=n/2;i>=0;i--){
keepHeap(data, n, i);
}
while (n > 0) {
swap(data, 0, n-1);
keepHeap(data, --n, 0);
}
}
private static void keepHeap(Number[] a, int n, int i) {
Number x = a[i];
int j = 2 * i + 1;
while (j <= n - 1) {
if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())
++j;
if (a[j].doubleValue() > x.doubleValue()) {
a[i] = a[j];
i = j;
j = 2 * i ;
} else{
break;
}
}
a[i] = x;
}
/**
* 歸并排序法————歸并排序
* @param data
*/
public static void 歸并排序(Number[] data)
{
Number[] result = merge_sort(data,0,data.length-1);
for(int i=0;i<result.length;i++){
data[i]=result[i];
}
}
private static Number[] merge_sort(Number[] array, int start, int end){
Number[] result = new Number[end-start+1];
if(start< end){
int mid= (start+end)/2;
Number[] left= merge_sort(array, start, mid);
Number[] right = merge_sort(array, mid+1, end);
result= merge(left,right);
} else if (start == end) {
result[0] = array[start];
return result;
}
return result;
}
private static Number[] merge(Number[] left, Number[] right) {
Number[] result = new Number[left.length+right.length];
int i=0;
int j=0;
int k=0;
while(i< left.length&&j< right.length){
if(left[i].doubleValue()< right[j].doubleValue()){
result[k++] = left[i++];
}else{
result[k++] = right[j++];
}
}
while(i< left.length){
result[k++] = left[i++];
}
while (j< right.length) {
result[k++]= right[j++];
}
return result;
}
/**
* 交換數(shù)組中指定的兩元素的位置
* @param data
* @param x
* @param y
*/
private static void swap(Number[] data, int x, int y) {
Number temp = data[x];
data[x] = data[y];
data[y] = temp;
}
}

posted on 2011-05-24 23:58 大魚閱讀(1803) 評(píng)論(0) 編輯收藏所屬分類: j2se

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問(wèn) 管理
相關(guān)文章: 排序算法java版，速度排行：冒泡排序、簡(jiǎn)單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序用Java讀取Properties文件的六種方法 Java實(shí)現(xiàn)四則運(yùn)算的解析收藏 23種設(shè)計(jì)模式有趣的介紹 JDOM解析XML字符串(非XML文檔) JVM調(diào)優(yōu)總結(jié) -Xms -Xmx -Xmn -Xss ActiveX控件打包成Cab置于網(wǎng)頁(yè)中自動(dòng)下載安裝 Java內(nèi)存溢出的詳細(xì)解決方案 java中的時(shí)間轉(zhuǎn)換及時(shí)間對(duì)比 java中的值傳遞和引用傳遞

大魚

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

收藏夾

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

排序算法java版，速度排行：冒泡排序、簡(jiǎn)單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序