利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc

利用利用 JAVA 實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法 在網(wǎng)上看的 挺全的 收了先 在網(wǎng)上看的 挺全的 收了先 第十章第十章 排序排序 源程序 源程序 Data java package Sort class Data Comparable key Object value public Data public Data Data data this key data key this value data value public Data Comparable key Object value this key key this value value public String toString return key key value value n Insertion java package Sort public class InsertionSort public InsertionSort 直接插入排序直接插入排序 從下標從下標 1 開始開始 public static void straightInsertionSort Data data int i j for i 2 i data length i if data i pareTo data i 1 key 0 data 0 data i 復(fù)制為監(jiān)視哨 for j i 1 data 0 pareTo data j key 0 j data j 1 data j 記錄右移 data j 1 data 0 插入 折半插入排序折半插入排序 從下標從下標 1 開始開始 public static void BinaryInsertionSort Data data int i j low high mid for i 2 i data length i if data i pareTo data i 1 key 0 data 0 data i 找插入位置 low 1 high i 1 while low high mid low high 2 if data 0 pareTo data mid key high 1 j data j 1 data j data high 1 data 0 插入 表插入排序表插入排序 public static void ListInsertionSort Data data int i j k inner class Table class Table Comparable key int next Table table new Table data length for i 1 i data length i table i new Table table i key data i key table 0 new Table table 0 key new Integer Integer MAX VALUE table 0 next 1 table 1 next 0 for i 2 i data length i for j 0 k table 0 next table k pareTo table i key 0 j k k table k next table j next i table i next k Data newData new Data data length int position table 0 next for i 1 i data length i newData i data position position table position next data newData 不知為什么不能把 newData 賦給 data 而必須用下面的 for i 1 i 1 lastChangeIndex 1 for j 1 j i j if data j 1 pareTo data j key 0 temp data j 1 data j 1 data j data j temp lastChangeIndex j i lastChangeIndex 快速排序 public static void QuickSort Data data QSort data 1 data length 1 public static void OptimizeQuickSort Data data OQSort data 1 data length 1 private static void QSort Data data int s int t int pivotLoc if s t pivotLoc Partition data s t 對 data 1 data length 1 進行一次劃分 QSort data s pivotLoc 1 對低子序列進行遞歸排序 QSort data pivotLoc 1 t 對高子序列進行遞歸排序 private static void OQSort Data data int s int t int pivotLoc if s t pivotLoc RandomPartition data s t QSort data s pivotLoc 1 對低子序列進行遞歸排序 QSort data pivotLoc 1 t 對高子序列進行遞歸排序 private static int RandomPartition Data data int low int high i 是 low int i int Math random high low low Data temp data low data low data i data i temp return Partition data low high private static int Partition Data data int low int high Comparable pivotKey data 0 data low pivotKey data low key 樞軸 while low high while low 0 high data low data high while low high i HeapAdjust data i data length 1 建立大頂堆 for i data length 1 i 1 i temp data 1 data 1 data i data i temp HeapAdjust data 1 i 1 private static void HeapAdjust Data data int start int end int j Data temp temp data start for j 2 start j end j 2 if j end data start data j start j data start temp 簡單選擇排序 public static void SimpleSelectSort Data data int i j Data temp for i 1 i data length i j MinKey data i if j i temp data i data i data j data j temp private static int MinKey Data data int start int i j start Comparable temp temp data start key if data length start 0 return start for i start 1 i 0 temp data i key j i return j 歸并排序 private static Data originalnewData2 private static Data newData2 public static void MergingSort Data data originalnewData2 new Data data length newData2 new Data data length for int i 1 i data length i originalnewData2 i new Data newData2 i new Data MSort data data 1 data length 1 private static void MSort Data originalData Data data int start int end if start end data start originalData start else int mid start end 2 MSort originalData newData2 start mid MSort originalData newData2 mid 1 end 怎樣才能像值傳遞一樣使用引用傳遞 即不改變它的值 for int k start k end k originalnewData2 k new Data newData2 k merge originalnewData2 data start mid end 這里的 data 好像不再是一開始傳入的 data 而是遞歸時的 newData2 private static void merge Data newData Data data int start int mid int end int i j int k start for i start j mid 1 start mid i if newData start pareTo newData j key 0 data i newData start else data i newData j if start mid for int tempI start tempI mid tempI data i newData tempI if j end for int tempJ j tempJ end tempJ data i newData tempJ 基數(shù)排序 public static void RadixSort Data data int digits int d j k factor 1 QueueInterface queues new LinkQueue 10 for int i 0 i 10 i queues i new LinkQueue for d 1 d digits factor 10 d distribution for j 1 j data length j queues Integer data j key intValue factor 10 put new Data data j collection for j 0 k 1 j 10 j while queues j isEmpty data k Data queues j removeHead 測試類 測試類 package Sort public class Test public Test 產(chǎn)生測試數(shù)據(jù) public static Data getData int size Data data new Data size 1 int number for int i 0 i data length i number int Math random size 10 data i new Data new Integer number new Integer number return data 復(fù)制測試數(shù)據(jù) public static Data duplicatio