数据结构课程设计之java排序.doc

数据结构课程设计专业:计算机科学与技术姓名：周兵学号:一、 需求分析一、设计代码：1. 直接插入排序：public class InsertSort public static T extends Comparable void insertSort(T array) for (int i = 1; i =1 & pareTo(arrayj - 1) 0) T temp = 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.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 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 high + 1; j-) tempj = tempj - 1; temphigh + 1 = tempVal; public static void 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 sortedLen= sorted.length; for(int j=inc+1;jsortedLen;j+ ) if(sortedj=0;k-=inc) if(sortedksorted0) sortedk+inc=sortedk; if(k-inc=0) insertPos = k; else insertPos=k+inc; break; sortedinsertPos=sorted0; public void shellInsertionSort(double sorted) int incs=7,5,3,1; int num= incs.length; int inc=0; for(int j=0;jnum;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(Before Sort:); for(int j=1;jarraysize;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;jsorted.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 xi + 1) temp = xi;xi = xi + 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.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);QuickExchangeSortBackTrack(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 = sorted0)-high;sortedlow = sortedhigh;while (low high & 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+) sortedj = (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 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;jsortedLen;j+) int jMin= getMinIndex(sorted,j); exchange(sorted,j,jMin); public void exchange(double sorted,int i,int j) int sortedLen= sorted.length; if(isortedLen & jsortedLen & i=0 & j=0) double temp= sortedi; sortedi=sortedj; sortedj=temp; public int getMinIndex(double sorted, int i) int sortedLen= sorted.length; int minJ=1; double min= Double.MAX_VALUE; for(int j=i;jsortedLen;j+) if(sortedjmin) 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;jarraysize;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;jsorted.length;j+) System.out.print(int)sortedj+ ); System.out.println(); 实验结果：7. 堆排序：public class SelectionSort public void heapAdjust(double sorted,int start,int end) if(startend) double temp= sortedstart; for(int j=2*start;jend;j *=2) if(j+110e-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(isortedLen & jsortedLen & i=0 & j=0) double temp= sortedi; sortedi=sortedj; sortedj=temp; public void heapSelectionSort(double sorted) int sortedLen = sorted.length; for(int i=sortedLen/2;i0;i-) heapAdjust(sorted,i,sortedLen); for(int i=sortedLen;i1;-i) exchange(sorted,1,i); heapAdjust(sorted,1,i-1); 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;jarraysize;j+) sortedj= (int)(random.nextDouble()* 100); System.out.print(int)sortedj+ ); System.out.println(); System.out.println(-); SelectionSort sorter=new SelectionSort(); sorter.heapSelectionSort(sorted); System.out.println(排序后:); for(int j=1;jsorted.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) throw 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, center); 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+; 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(String 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.out.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 VectorVector util; public void distribute(double sorted, int nth) if(nth0) util=new VectorVector(); for(int j=0;j10;j+) Vector temp= new Vector (); util.add(temp); for(int j=0;j=nth) return Character.getNumericValue(nn.charAt(len-nth); else return 0; public void collect(double sorted) int k=0; for(int j=0;j0) for(int i=0;ilen;i+) sortedk+= util.get(j).get(i); util=null; public int getKeyNum(double sorted) double max= Double.MIN_VALUE; for(int j=0;jmax) max= sortedj; return Integer.toString(int)max).length(); public void radixSort(double sorted) if(keyNum=-1) keyNum= getKeyNum(sorted); for(int i=1;i=keyNum;i+) distribute(sorted,i); collect(sorted); public static void main(String 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.out.println(-); RadixSort sorter = new RadixSort(); sorter.radixSort(sorted); System.out.println(排序后:); for (int j = 0; j sorted.length; j+) System.out.print(int) sortedj + ); System.out.println(); 实验结果：二、课程设计总结通过这次课程设计，加深了我对数据结构这门功课的结识，更加加深了我对程序算法的理解。我觉得课程设计这种形式是我们真正需要的，可以让我们学到很多，涉及书上的、书外的。而有一句话给我的体会是最深的，就是 理论！=实际。在学排序算法的时候，读了书上的算法描述，觉得自己都会了，考试的题目也做出来了，但真的到编程去实现的时候，却不是一次就能成功的，总会出点差错，等到程序终于能运营的时候，才真正体会到这些算法的精髓。理论和实际永远相差那么一点，不去实现是体会不出来的。在这里，当然还要感谢知道指导老师的辛勤教导，让我对数据结构有了更深的体会和理解，让我知道了怎么在实践中去应用算法，算法给程序带来的好处与效率等等。再次感谢老师的教导！