数据结构课程设计之java排序参考模板

1、 数据结构课程设计专业:计算机科学与技术姓名：周兵学号:0309401221 / 171、 需求分析一、设计代码：1. 直接插入排序：public class InsertSort public static <T extends Comparable<? super T>> void insertSort(T array) for (int i = 1; i <= array.length - 1; i+) int j = i; while (j>=1 && pareTo(arrayj - 1) < 0) T te

2、mp = arrayj; arrayj = arrayj - 1; arrayj - 1 = temp; j-; public static void main(String args) Integer testArray = 23, 25, 12, 42, 35,33,43,57; System.out.println("排序前 :"); for (Integer item : testArray) System.out.print(item); System.out.print(' '); System.out.println(); System.out

3、.println("-"); InsertSort.insertSort(testArray); System.out.println("排序后 :"); for (Integer item : testArray) System.out.print(item); System.out.print(' '); 实验结果：2. 折半插入排序：public class BInsertSort public static void bInsertSort(int temp) int length = temp.length; for (int

4、i = 1; i < length; i+) int tempVal = tempi; int low = 0; int high = i - 1; while (low <= high) int middle = (low + high) / 2; if (tempVal < tempmiddle) high = middle - 1; else low = middle + 1; for (int j = i; j > high + 1; j-) tempj = tempj - 1; temphigh + 1 = tempVal; public static voi

5、d main(String args) int a = 5, 1, 76, 2, 4, 84, 36, 22, 62, 90 ; bInsertSort(a); System.out.println("排序后:"); for (int i = 0; i < a.length; i+) System.out.print(ai + " "); 实验结果：3. 希尔排序:public class InsertionSort public void shellInertionSort(double sorted, int inc) int sortedLe

6、n= sorted.length; for(int j=inc+1;j<sortedLen;j+ ) if(sortedj<sortedj-inc) sorted0= sortedj;/先保存一下后面的那个 int insertPos=j; for(int k=j-inc;k>=0;k-=inc) if(sortedk>sorted0) sortedk+inc=sortedk; if(k-inc<=0) insertPos = k; else insertPos=k+inc; break; sortedinsertPos=sorted0; public void

7、shellInsertionSort(double sorted) int incs=7,5,3,1; int num= incs.length; int inc=0; for(int j=0;j<num;j+) inc= incsj; shellInertionSort(sorted,inc); public static void main(String args) Random random= new Random(6); int arraysize= 21; double sorted=new doublearraysize; System.out.print("Bef

8、ore Sort:"); for(int j=1;j<arraysize;j+) sortedj= (int)(random.nextDouble()* 100); System.out.print(int)sortedj+" "); System.out.println(); InsertionSort sorter=new InsertionSort(); sorter.shellInsertionSort(sorted); System.out.print("After Sort:"); for(int j=1;j<sorte

9、d.length;j+) System.out.print(int)sortedj+" "); System.out.println();实验结果：4. 冒泡排序：public class BubbluSort public static void sortiere(int x) boolean unsortiert = true;int temp;while (unsortiert) unsortiert = false;for (int i = 0; i < x.length - 1; i+)if (xi > xi + 1) temp = xi;xi = x

10、i + 1;xi + 1 = temp;unsortiert = true;public static void main(String args) int liste = 0, 9, 4, 6, 2, 8, 5, 1, 7, 3 ;System.out.println("排序前：");for (int i = 0; i < liste.length; i+)System.out.print(listei + " ");System.out.println();System.out.println("-");System.out

11、.println("排序后：");sortiere(liste);for (int i = 0; i < liste.length; i+)System.out.print(listei + " "); 实验结果：5. 快速排序：public class ExchangeSort public void QuickExchangeSortBackTrack(double sorted,int low, int high) if (low < high) int pivot = findPivot(sorted, low, high);Quic

12、kExchangeSortBackTrack(sorted, low, pivot - 1);QuickExchangeSortBackTrack(sorted, pivot + 1, high);public int findPivot(double sorted, int low, int high) sorted0 = sortedlow;while (low < high) while (low < high && sortedhigh >= sorted0)-high;sortedlow = sortedhigh;while (low < hi

13、gh && sortedlow <= sorted0)+low;sortedhigh = sortedlow;sortedlow = sorted0;return low;public static void main(String args) Random random = new Random(6);int arraysize = 10;double sorted = new doublearraysize;System.out.println("排序前:");for (int j = 1; j < arraysize; j+) sorted

14、j = (int) (random.nextDouble() * 100);System.out.print(int) sortedj + " ");System.out.println();System.out.println("-");ExchangeSort sorter = new ExchangeSort();sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize - 1);System.out.println("排序后:");for (int j = 1; j <

15、 sorted.length; j+) System.out.print(int) sortedj + " ");System.out.println();实验结果：6. 直接选择排序：public class SelectionSort public void straitSelectionSort(double sorted) int sortedLen= sorted.length; for(int j=1;j<sortedLen;j+) int jMin= getMinIndex(sorted,j); exchange(sorted,j,jMin); publ

16、ic void exchange(double sorted,int i,int j) int sortedLen= sorted.length; if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0) double temp= sortedi; sortedi=sortedj; sortedj=temp; public int getMinIndex(double sorted, int i) int sortedLen= sorted.lengt

17、h; int minJ=1; double min= Double.MAX_VALUE; for(int j=i;j<sortedLen;j+) if(sortedj<min) min= sortedj; minJ= j; return minJ; public static void main(String args) Random random= new Random(6); int arraysize=9; double sorted=new doublearraysize; System.out.println("排序前:"); for(int j=1;

18、j<arraysize;j+) sortedj= (int)(random.nextDouble()* 100); System.out.print(int)sortedj+" "); System.out.println(); System.out.println("-"); SelectionSort sorter=new SelectionSort(); sorter.straitSelectionSort(sorted); System.out.println("排序后:"); for(int j=1;j<sort

19、ed.length;j+) System.out.print(int)sortedj+" "); System.out.println(); 实验结果：7. 堆排序：public class SelectionSort public void heapAdjust(double sorted,int start,int end) if(start<end) double temp= sortedstart; for(int j=2*start;j<end;j *=2) if(j+1<end && sortedj-sortedj+1>1

20、0e-6) +j; if(temp<=sortedj) break; sortedstart=sortedj; start=j; sortedstart=temp; public void exchange(double sorted,int i,int j) int sortedLen= sorted.length; if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0) double temp= sortedi; sortedi=sorte

21、dj; sortedj=temp; public void heapSelectionSort(double sorted) int sortedLen = sorted.length; for(int i=sortedLen/2;i>0;i-) heapAdjust(sorted,i,sortedLen); for(int i=sortedLen;i>1;-i) exchange(sorted,1,i); heapAdjust(sorted,1,i-1); public static void main(String args) Random random= new Random

22、(6); int arraysize=10; double sorted=new doublearraysize; System.out.println("排序前:"); for(int j=1;j<arraysize;j+) sortedj= (int)(random.nextDouble()* 100); System.out.print(int)sortedj+" "); System.out.println(); System.out.println("-"); SelectionSort sorter=new Sele

23、ctionSort(); sorter.heapSelectionSort(sorted); System.out.println("排序后:"); for(int j=1;j<sorted.length;j+) System.out.print(int)sortedj+" "); System.out.println(); 实验结果：8. 归并排序:public class MergeSort private double bridge;/辅助数组 public void sort(double obj) if (obj = null) thro

24、w new NullPointerException("The param can not be null!"); bridge = new doubleobj.length; / 初始化中间数组 mergeSort(obj, 0, obj.length - 1); / 归并排序 bridge = null; private void mergeSort(double obj, int left, int right) if (left < right) int center = (left + right) / 2; mergeSort(obj, left, cen

25、ter); mergeSort(obj, center + 1, right); merge(obj, left, center, right); private void merge(double obj, int left, int center, int right) int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= right) if (objleft-objmid<=10e-6) bridgethird+ = objleft+

26、; else bridgethird+ = objmid+; while (mid <= right) bridgethird+ = objmid+; while (left <= center) bridgethird+ = objleft+; / 将中间数组的内容拷贝回原数组 copy(obj, tmp, right); private void copy(double obj, int left, int right) while (left <= right) objleft = bridgeleft; left+; public static void main(S

27、tring args) Random random = new Random(6); int arraysize = 10; double sorted = new doublearraysize; System.out.println("排序前:"); for (int j = 0; j < arraysize; j+) sortedj = (int) (random.nextDouble() * 100); System.out.print(int) sortedj + " "); System.out.println(); System.ou

28、t.println("-"); MergeSort sorter = new MergeSort(); sorter.sort(sorted); System.out.println("排序后:"); for (int j = 0; j < sorted.length; j+) System.out.print(int) sortedj + " "); System.out.println(); 实验结果：9. 基数排序：public class RadixSort private int keyNum=-1; private

29、Vector<Vector<Double>> util; public void distribute(double sorted, int nth) if(nth<=keyNum && nth>0) util=new Vector<Vector<Double>>(); for(int j=0;j<10;j+) Vector <Double> temp= new Vector <Double>(); util.add(temp); for(int j=0;j<sorted.lengt

30、h;j+) int index= getNthDigit(sortedj,nth); util.get(index).add(sortedj); public int getNthDigit(double num,int nth) String nn= Integer.toString(int)num); int len= nn.length(); if(len>=nth) return Character.getNumericValue(nn.charAt(len-nth); else return 0; public void collect(double sorted) int k

31、=0; for(int j=0;j<10;j+) int len= util.get(j).size(); if(len>0) for(int i=0;i<len;i+) sortedk+= util.get(j).get(i); util=null; public int getKeyNum(double sorted) double max= Double.MIN_VALUE; for(int j=0;j<sorted.length;j+) if(sortedj>max) max= sortedj; return Integer.toString(int)max).length();