排序算法時間復雜度比較.doc

12 排序算法比較主要內(nèi)容： 1)利用隨機函數(shù)產(chǎn)生10000個隨機整數(shù)，對這些數(shù)進行多種方法排序。 2）至少采用4種方法實現(xiàn)上述問題求解（可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序），并把排序后的結(jié)功能果保存在不同的文件里。 3）給出該排序算法統(tǒng)計每一種排序方法的性能（以運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。程序的主要功能：1.隨機數(shù)在排序函數(shù)作用下進行排序2.程序給出隨機數(shù)排序所用的時間。算法及時間復雜度（一）各個排序是算法思想：（1）直接插入排序：將一個記錄插入到已排好的有序表中，從而得到一個新的，記錄數(shù)增加1的有序表。（2）冒泡排序：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關(guān)鍵字。依此類推，直到第N-1和第N個記錄的關(guān)鍵字進行過比較為止。上述為第一趟排序，其結(jié)果使得關(guān)鍵字的最大紀錄被安排到最后一個記錄的位置上。然后進行第二趟起泡排序，對前N-1個記錄進行同樣操作。一共要進行N-1趟起泡排序。（3）快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，已達到整個序列有序。（4）選擇排序：通過N-I次關(guān)鍵字間的比較，從N-I+1個記錄中選出關(guān)鍵字最小的記錄，并和第I（1=I=N）個記錄交換。時間復雜度分析排序算法 最差時間時間復雜度 是否穩(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個數(shù)據(jù)的時間比較：算法名稱用時插入排序122冒泡排序343快速排序7選擇排序116程序源代碼：/*package test;public class SortArray private static final int Min = 1;/生成隨機數(shù)最小值 private static final int Max = 10000;/生成隨機數(shù)最大值 private static final int Length = 10000;/生成隨機數(shù)組長度(測試的朋友建議不要超過40000,不然你要等很久,如果你電腦配置絕對高的情況下你可以再加個0試試) public static void main(String args) System.out.println(數(shù)組長度：+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(插入法排序法消耗時間:+(end-begin)+毫秒); begin = System.currentTimeMillis(); bubbleSort(arr.clone(); end = System.currentTimeMillis(); System.out.println(冒泡發(fā)排序法消耗時間:+(end-begin)+毫秒); begin = System.currentTimeMillis(); fastSort(arr.clone(),0,arr.length-1); end = System.currentTimeMillis(); System.out.println(快速排序法消耗時間:+(end-begin)+毫秒); begin = System.currentTimeMillis(); choiceSort(arr.clone(); end = System.currentTimeMillis(); System.out.println(選擇排序法消耗時間:+(end-begin)+毫秒); /*生成隨機數(shù)數(shù)組 * param length 數(shù)組長度 * 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ù)組最小下標(一般是0) * param right 數(shù)組最大下標(一般是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; /對左面進行遞歸 fastSort(arr,left,j-1); /對右面進行遞歸 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+) /比較兩個相鄰的元素 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個元素比第m個元素小，將j賦值給m if(arrj arrm) m = j; /交換m和i兩個元素的位置 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+,); 測試結(jié)果：總結(jié)：好的算法編程技巧高效率好的程序。1、 做什么都需要耐心，做設(shè)計寫程序則更需要耐心。一開始的時候，好不容易寫好了程序，可是等最后調(diào)試的時候發(fā)現(xiàn)錯誤很隱蔽，就很費時間了。后來我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，先把各小部分編好才編主函數(shù),考慮好接口之后才動手編，這樣就比較容易成功了。2、 做任何事情我決定都應(yīng)該有個總體規(guī)劃。之后的工作按照規(guī)劃逐步展開完成。對于一個完整的程序設(shè)計，首先需要總體規(guī)劃寫