(java排序算法代码大全.docxVIP

java 排序算法代码大全 2012-04-17 14:58:02| 分类： JAVA 知识积累 |字号 订阅/** * 插入排序:直接插入排序、折半插入排序和系尔排序 * 交换排序:冒泡排序和快速排序 * 选择排序:简单选择排序和堆排序 * 归并排序:归并排序 * * 基本思想 * 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。 * 交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。 * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。 * * 排序方法比较 * 排序方法 平均时间 最坏时间 辅助存储 * 直接插入排序 O(N2) O(N2) O(1) * 起泡排序 O(N2) O(N2) O(1) * 快速排序 O(Nlog2N) O(N2) O(Nlog2N) * 简单选择排序 O(N2) O(N2) O(1) * 堆排序 O(Nlog2N) O(Nlog2N) O(1) * 归并排序 O(Nlog2N) O(Nlog2N) O(n) * 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix) * * * * @author Administrator * */ public class SortTest { public static void main(String[] args)throws Exception { //测试排序是否正确 //String[] testErr=new String[]{冒泡排序,简单选择排序,直接插入排序,折半插入排序,系尔排序,堆排序,归并排序,快速排序}; //new SortTest().testErr(testErr); //排序1（全部） String[] strs=new String[]{冒泡排序,简单选择排序,直接插入排序,折半插入排序,希尔排序,堆排序,归并排序,快速排序}; new SortTest().test(strs,10000,50000,5000); //排序2（加强） String[] strs2=new String[]{希尔排序,堆排序,归并排序,快速排序}; new SortTest().test(strs2,100000,1900000,100000); }private void testErr(String[] strings) throws Exception{ //System.out.println(Arrays.toString(old)); System.out.println(Arrays.toString(strings)); Number[] old=getRundom(50); Integer[] oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21}; old=oo; for(String s:strings){ Number[] testNum=Arrays.copyOf(old, old.length); long begin=System.currentTimeMillis(); SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum); long end=System.currentTimeMillis(); System.out.println(s+:+(end-begin)+\t); System.out.println(Arrays.toString(testNum)); } System.out.println(); } private void test(String[] strings,long begin,long end,long step) throws Exception{ System.out.print(数量\t); for(String str:strings){ System.out.print(str+\t); } System.out.println(); for(long i=begin;iend;i=i+step){ System.out.print(i+个