排序算法時(shí)間復(fù)雜度比較

1、排序算法比較主要容：1）利用隨機(jī)函數(shù)產(chǎn)生 10000 個(gè)隨機(jī)整數(shù)，對(duì)這些數(shù)進(jìn)行多種方法 排序。2 ）至少采用 4種方法實(shí)現(xiàn)上述問題求解 （可采用的方法有插入排 序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）， 并把排序后的結(jié)功能果保存在不同的文件里。3 ）給出該排序算法統(tǒng)計(jì)每一種排序方法的性能 （以運(yùn)行程序所花 費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比） ，找出其中兩種較快的方法。程序的主要功能：1. 隨機(jī)數(shù)在排序函數(shù)作用下進(jìn)行排序2. 程序給出隨機(jī)數(shù)排序所用的時(shí)間。算法及時(shí)間復(fù)雜度（一）各個(gè)排序是算法思想：（1）直接插入排序：將一個(gè)記錄插入到已排好的有序表中，從而得 到一個(gè)新的，記錄數(shù)增加 1

2、的有序表。（2）冒泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字 進(jìn)行比較，若為逆序， 則將兩個(gè)記錄交換， 然后比較第二個(gè)記錄 和第三個(gè)記錄的關(guān)鍵字。 依此類推，直到第 N-1 和第 N 個(gè)記錄的 關(guān)鍵字進(jìn)行過比較為止。 上述為第一趟排序， 其結(jié)果使得關(guān)鍵字 的最大紀(jì)錄被安排到最后一個(gè)記錄的位置上。 然后進(jìn)行第二趟起 泡排序，對(duì)前 N-1 個(gè)記錄進(jìn)行同樣操作。 一共要進(jìn)行 N-1 趟起泡 排序。3）快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其 中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小， 則可分別 對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。4）選擇排序：通過 N-I

3、次關(guān)鍵字間的比較，從 N-I+1 個(gè)記錄中選 出關(guān)鍵字最小的記錄，并和第 I （1=I=N）個(gè)記錄交換。時(shí)間復(fù)雜度分析排序算法最差時(shí)間時(shí)間復(fù)雜度是否穩(wěn)定？插入排序O(n2)O(n2)穩(wěn)定冒泡排序O(n2)O(n2)穩(wěn)定快速排序O(n2)O(n*log 2n)不穩(wěn)定選擇排序O(n2)O(n2)穩(wěn)定10000 個(gè)數(shù)據(jù)的時(shí)間比較：算法名稱用時(shí)插入排序122冒泡排序343快速排序7選擇排序116程序源代碼：package test;public class SortArray private static final int Min = 1;/生成隨機(jī)數(shù)最小值private static final

4、int Max = 10000;/生成隨機(jī)數(shù)最大值private static final int Length = 10000;/ 生成隨機(jī)數(shù)組長(zhǎng)度 ( 測(cè) 試的朋友建議不要超過 40000,不然你要等很久 , 如果你電腦配置絕對(duì) 高的情況下你可以再加個(gè) 0 試試)public static void main(String args) 數(shù)組長(zhǎng)度： +Length+, Min ： +Min+, Max：+Max);long begin;long end;int arr = getArray(Length);begin = System.currentTimeMillis();insertSo

5、rt(arr.clone();end = System.currentTimeMillis();插入法排序法消耗時(shí)間 :+(end-begin)+ 毫秒);begin = System.currentTimeMillis();bubbleSort(arr.clone();end = System.currentTimeMillis();冒泡發(fā)排序法消耗時(shí)間 :+(end-begin)+ 毫秒);begin = System.currentTimeMillis();fastSort(arr.clone(),0,arr.length-1);end = System.currentTimeMilli

6、s();快速排序法消耗時(shí)間 :+(end-begin)+ 毫 秒);begin = System.currentTimeMillis(); choiceSort(arr.clone();end = System.currentTimeMillis();System.out.println(選擇排序法消耗時(shí)間 :+(end-begin)+ 毫秒);/* 生成隨機(jī)數(shù)數(shù)組* param length數(shù)組長(zhǎng)度* return int*/private static int getArray(int length)if(length=0)return null;int arr = new intleng

7、th;for (int i = 0; i arr.length; i+) int temp = (int)(Min+Math.random()*(Max-Min-1);arri = temp;return arr;/* 快速發(fā)排序* param arr需要排序的數(shù)組* param left數(shù)組最小下標(biāo) ( 一般是 0)* param right 數(shù)組最大下標(biāo) ( 一般是 Length-1)* return int*/right)private static int fastSort(int arr,int left,int if(left right)int s = arrleft;int i

8、 = left;int j = right + 1;while(true)/ 向右找大于 s 的元素的索引 while(i+1 arr.length & arr+i -1 & arr-j s);/如果 i = j 推出循環(huán)if(i = j)break;else/ 教化 i 和 j 位置的元素int t = arri;arri = arrj;arrj = t;arrleft = arrj;arrj = s;/對(duì)左面進(jìn)行遞歸fastSort(arr,left,j-1);/對(duì)右面進(jìn)行遞歸fastSort(arr,j+1,right);return arr;/* 插入法排序* param arr 需要

9、排序的數(shù)組* return int*/private static int insertSort(int arr) for(int i = 1;i arr.length;i+) int temp = arri;int j = i - 1; while(temp arrj) arrj+1 = arrj; j-;if(j = -1)break;arrj+1 = temp;return arr;/* 冒泡發(fā)排序* param arr 需要排序的數(shù)組* return int*/private static int bubbleSort(int arr) for(int i = 0;i arr.leng

10、th;i+)/ 比較兩個(gè)相鄰的元素 for(int j = 0;j arrj+1) int t = arrj;arrj = arrj+1; arrj+1 = t; return arr;/* 選擇法排序* param arr* return*/private static int choiceSort(int arr)for(int i = 0;i arr.length;i+)int m = i;for(int j = i + 1;j arr.length;j+)/ 如果第 j 個(gè)元素比第 m 個(gè)元素小，將 j 賦值給 mif(arrj arrm)m = j;/交換 m和 i 兩個(gè)元素的位置i

11、f(i != m)int t = arri;arri = arrm;arrm = t;return arr; 経“翦腺鴇卅im 蛀a飩im細(xì)聽昌 龍皿:卵孵段f懈丫專 0000T 卿 ri 巴w *00001 ：okk fcwsii aerklTifrTE)GTIwAy uiPJfioJd uai|ddv awfl eq i Jo = !屮!)j Juj niej(o=二屮 6uerjje| nu=jje)ji (jjb uiuud piOA 5冋s eieAud馬誨軸由耳壷峑e mejed .馬誨由丄* */總結(jié)：好的算法編程技巧高效率好的程序。1、做什么都需要耐心，做設(shè)計(jì)寫程序則更需要耐心。一開始的 時(shí)候，好不容易寫好了程序， 可是等最后調(diào)試的時(shí)候發(fā)現(xiàn)錯(cuò)誤很隱蔽， 就很費(fèi)時(shí)間了。 后來我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)， 先把各小 部分編好才編主函數(shù) , 考慮好接口之后才動(dòng)手編，這樣就比較容易成 功了。2、做任何事情我決定都應(yīng)該有個(gè)總體規(guī)劃。之后的工作按照規(guī) 劃逐步展開完成。 對(duì)于一個(gè)完整的程序設(shè)計(jì)， 首先需要總體規(guī)劃寫程 序的步驟，分塊寫