利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc_第1頁
利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc_第2頁
利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc_第3頁
利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc_第4頁
利用JAVA實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中常用的插入排序和快速排序算法.doc_第5頁
已閱讀5頁,還剩7頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

利用利用 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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論