利用JAVA实现数据结构中常用的插入排序和快速排序算法.doc

利用利用 JAVA 实现数据结构中常用的插入排序和快速排序算法实现数据结构中常用的插入排序和快速排序算法 在网上看的 挺全的 收了先 在网上看的 挺全的 收了先 第十章第十章 排序排序 源程序 源程序 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 复制为监视哨 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 基数排序 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 产生测试数据 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 复制测试数据 public static Data duplicatio