<ul id="assyy"></ul>

<strike id="assyy"><menu id="assyy"></menu></strike>

<ul id="assyy"><sup id="assyy"></sup></ul>

大魚

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

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

本文思路部分來源于上篇文章，但測得的結果似乎不大相同，不知是因為java的緣故還是因為我算法的緣故，歡迎拍磚。

復習排序，順便比下各種算法的速度，榜單如下：

1、冒泡排序

2、簡單選擇排序

3、直接插入排序

4、折半插入排序

5、希爾排序

6、堆排序

7、歸并排序

8、快速排序

當然這是慢速排行，哈哈~~

直接上圖：單位毫秒

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

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

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

補上代碼：

Java代碼  
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
/** 
* 插入排序:直接插入排序、折半插入排序和系爾排序 
* 交換排序:冒泡排序和快速排序 
* 選擇排序:簡單選擇排序和堆排序 
* 歸并排序:歸并排序 
* 
* 基本思想 
* 插入排序:將第N個記錄插入到前面(N-1)個有序的記錄當中。 
* 交換排序:按照某種順序比較兩個記錄的關鍵字大小，然后根據需要交換兩個記錄的位置。 
* 選擇排序:根據某種方法選擇一個關鍵字最大的記錄或者關鍵字最小的記錄，放到適當的位置。 
* 
* 排序方法比較 
* 排序方法 平均時間 最壞時間 輔助存儲 
* 直接插入排序 O(N2) O(N2) O(1) 
* 起泡排序 O(N2) O(N2) O(1) 
* 快速排序 O(Nlog2N) O(N2) O(Nlog2N) 
* 簡單選擇排序 O(N2) O(N2) O(1) 
* 堆排序 O(Nlog2N) O(Nlog2N) O(1) 
* 歸并排序 O(Nlog2N) O(Nlog2N) O(n) 
* 基數排序 O(d(n+radix)) O(d(n+radix)) O(radix) 
* 
* 
* 
* @author Administrator 
* 
*/ 
public class SortTest { 
public static void main(String[] args)throws Exception { 
//測試排序是否正確 
//String[] testErr=new String[]{"冒泡排序","簡單選擇排序","直接插入排序","折半插入排序","系爾排序","堆排序","歸并排序","快速排序"}; 
//new SortTest().testErr(testErr); 
//排序1（全部） 
String[] strs=new String[]{"冒泡排序","簡單選擇排序","直接插入排序","折半插入排序","希爾排序","堆排序","歸并排序","快速排序"}; 
new SortTest().test(strs,10000,50000,5000); 
//排序2（加強） 
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("數量\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+"個\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){ 
//組內直接插入排序 
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++) { 
//將相鄰兩個數進行比較，較大的數往后冒泡 
for (int j = 0; j < data.length - i-1; j++) { 
if (data[j].doubleValue()> data[j + 1].doubleValue()) { 
//交換相鄰兩個數 
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){ 
//取中點 
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); 
} 
} 
/** 
* 選擇排序————簡單選擇排序 
* @param data 
*/ 
public static void 簡單選擇排序(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; 
} 
/** 
* 交換數組中指定的兩元素的位置 
* @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-10-06 23:34 大魚閱讀(831) 評論(1) 編輯收藏所屬分類: 軟件工程

評論

# re: 排序算法java版，速度排行：冒泡排序、簡單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序 2011-10-07 19:35 安多

收藏了回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 需求分析報告 V 需求說明書 V 需求規格說明書的區別排序算法java版，速度排行：冒泡排序、簡單選擇排序、直接插入排序、折半插入排序、希爾排序、堆排序、歸并排序、快速排序 UML 繼承、實現、依賴、關聯、聚合、組合的聯系與區別必須知道的業務系統簡稱軟件開發文檔基本知識在項目開發過程中，應該按要求編寫好十三種文檔軟件開發管理十大工作任務可行性研究報告編寫規范詳細設計文檔規范概要設計和詳細設計的區別與聯系

主站蜘蛛池模板：沾益县| 厦门市| 台州市| 永城市| 五台县| 福安市| 边坝县| 九台市| 宁化县| 台北县| 济阳县| 祁东县| 团风县| 陆良县| 会东县| 阿图什市| 石河子市| 锡林浩特市| 阿瓦提县| 新竹县| 雅江县| 琼结县| 寿宁县| 屏边| 衡南县| 左云县| 区。| 黎川县| 康乐县| 沛县| 瓮安县| 宁河县| 泸水县| 同江市| 南岸区| 恭城| 乾安县| 平果县| 南华县| 弥渡县| 德令哈市|

<tfoot id="4ia2c"><input id="4ia2c"></input></tfoot>

<strike id="4ia2c"><input id="4ia2c"></input></strike>

<strike id="4ia2c"></strike>

<strike id="4ia2c"><input id="4ia2c"></input></strike>