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

12 排序算法比較主要內(nèi)容： 1)利用隨機(jī)函數(shù)產(chǎn)生10000個(gè)隨機(jī)整數(shù)，對(duì)這些數(shù)進(jìn)行多種方法排序。 2）至少采用4種方法實(shí)現(xiàn)上述問(wè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）冒泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。依此類推，直到第N-1和第N個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止。上述為第一趟排序，其結(jié)果使得關(guān)鍵字的最大紀(jì)錄被安排到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟起泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作。一共要進(jìn)行N-1趟起泡排序。（3）快速排序：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。（4）選擇排序：通過(guò)N-I次關(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*log2n) 不穩(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 int Max = 10000;/生成隨機(jī)數(shù)最大值 private static final int Length = 10000;/生成隨機(jī)數(shù)組長(zhǎng)度(測(cè)試的朋友建議不要超過(guò)40000,不然你要等很久,如果你電腦配置絕對(duì)高的情況下你可以再加個(gè)0試試) public static void main(String args) System.out.println(數(shù)組長(zhǎng)度：+Length+, Min：+Min+, Max：+Max); long begin; long end; int arr = getArray(Length); begin = System.currentTimeMillis(); insertSort(arr.clone(); end = System.currentTimeMillis(); System.out.println(插入法排序法消耗時(shí)間:+(end-begin)+毫秒); begin = System.currentTimeMillis(); bubbleSort(arr.clone(); end = System.currentTimeMillis(); System.out.println(冒泡發(fā)排序法消耗時(shí)間:+(end-begin)+毫秒); begin = System.currentTimeMillis(); fastSort(arr.clone(),0,arr.length-1); end = System.currentTimeMillis(); System.out.println(快速排序法消耗時(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 intlength; 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 */ private static int fastSort(int arr,int left,int right) if(left right) int s = arrleft; int i = 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 需要排序的數(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.length;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賦值給m if(arrj arrm) m = j; /交換m和i兩個(gè)元素的位置 if(i != m) int t = arri; arri = arrm; arrm = t; return arr; /*打印數(shù)組 * param arr 需要打印的數(shù)組 */ private static void print(int arr) if(arr=null|arr.length=0)return; for (int i = 0; i arr.length; i+) System.out.print(arri+,); 測(cè)試結(jié)果：總結(jié)：好的算法編程技巧高效率好的程序。1、 做什么都需要耐心，做設(shè)計(jì)寫(xiě)程序則更需要耐心。一開(kāi)始的時(shí)候，好不容易寫(xiě)好了程序，可是等最后調(diào)試的時(shí)候發(fā)現(xiàn)錯(cuò)誤很隱蔽，就很費(fèi)時(shí)間了。后來(lái)我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，先把各小部分編好才編主函數(shù),考慮好接口之后才動(dòng)手編，這樣就比較容易成功了。2、 做任何事情我決定都應(yīng)該有個(gè)總體規(guī)劃。之后的工作按照規(guī)劃逐步展開(kāi)完成。對(duì)于一個(gè)完整的程序設(shè)計(jì)，首先需要總體規(guī)劃寫(xiě)