排序算法java版(转载)

本文转自：   http://yiyickf.iteye.com/blog/1047010

 

 

复习排序，顺便比下各种算法的速度，榜单如下：

1、冒泡排序

2、简单选择排序

3、直接插入排序

4、折半插入排序

5、希尔排序

6、堆排序

7、归并排序

8、快速排序

当然这是慢速排行，哈哈~~

 

 

直接上图：单位毫秒

 

数量	冒泡排序	简单选择排序	直接插入排序	折半插入排序	希尔排序	堆排序	归并排序	快速排序
10000个	1578	1250	672	250	0	15	16	0
15000个	3453	2765	1563	531	16	15	16	0
20000个	6140	4547	2453	828	16	16	15	16
25000个	10079	7171	3969	1313	31	16	15	16
30000个	14641	10313	5578	1906	31	31	16	31
35000个	20141	14328	7890	2563	31	31	32	15
40000个	25766	18359	10094	3422	47	31	31	32
45000个	32469	24063	13062	4359	47	47	31	47

 

 

由于"希尔排序","堆排序","归并排序","快速排序"太快，以至于在上图几乎是条直线，故有了下面转为他们准备的加强版

 

数量	希尔排序	堆排序	归并排序	快速排序
100000个	172	140	110	93
200000个	469	406	235	234
300000个	812	703	422	375
400000个	1125	1031	516	531
500000个	1406	1282	719	656
600000个	1828	1703	860	859
700000个	2531	2063	1000	968
800000个	2735	2453	1140	1188
900000个	3047	2843	1391	1266
1000000个	3375	3187	1516	1422
1100000个	3922	3500	1625	1609
1200000个	4421	3954	1969	1812
1300000个	4797	4422	2000	1953
1400000个	5391	4797	2547	2094
1500000个	5437	5219	2625	2328
1600000个	6203	5546	2469	2485
1700000个	6532	5953	2844	2672
1800000个	7125	6421	2984	2844

 

补上代码：

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 插入排序:直接插入排序、折半插入排序和系尔排序
 * 交换排序:冒泡排序和快速排序
 * 选择排序:简单选择排序和堆排序
 * 归并排序:归并排序
 *
 * 基本思想
 * 插入排序:将第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;i<end;i=i+step){
            System.out.print(i+"个\t");
            Number[] old=getRundom(i);
            for(String s:strings){
                Number[] testNum=Arrays.copyOf(old, old.length);
                long beginTime=System.currentTimeMillis();
                SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);

                long endTime=System.currentTimeMillis();
                System.out.print((endTime-beginTime)+"\t");
                //System.out.println(Arrays.toString(testNum));
            }
            System.out.println();
        }

    }

    private static Integer[] getRundom(long num) {
        List<Integer> list=new ArrayList<Integer>();
        for(long i=0;i<num;i++){
            int k;
            if(Math.random()>0.5){
                k=(int)(Math.random()*Integer.MAX_VALUE);
            }else{
                k=(int)(Math.random()*Integer.MIN_VALUE);
            }
            list.add(k);
        }
        return list.toArray(new Integer[list.size()]);
    }




    /**
     * 插入排序————直接插入排序
     * @param data
     */
    public static  void  直接插入排序(Number[] data)
    {
        Number tmp=null ;

      for(int i=1;i<data.length;i++){
          tmp = data[i];
          int j=i-1;
          while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){
              data[j+1]=data[j];
              j--;
          }
          data[j+1]=tmp;
      }
    }
    /**
     * 插入排序————折半插入排序
     * @param data
     */
    public static  void  折半插入排序(Number[] data)
    {
        Number tmp=null ;
          for(int i=1;i<data.length;i++){
              tmp = data[i];
              int smallpoint=0;
              int bigpoint=i-1;

              while(bigpoint>=smallpoint){
                  int mid=(smallpoint+bigpoint)/2;
                  if(tmp.doubleValue()>data[mid].doubleValue()){
                      smallpoint=mid+1;
                  }else{
                      bigpoint=mid-1;
                  }
              }
              for(int j=i;j>smallpoint;j--){
                  data[j]=data[j-1];
              }
              data[bigpoint+1]=tmp;
          }
    }

    /**
     * 插入排序————希尔排序
     * @param data
     */
    public static  void  希尔排序(Number[] data)
    {
        int span=data.length/7;
        if(span==0)span=1;
        while(span>=1){
            for(int i=0;i<span;i++){
                for(int j=i;j<data.length;j=j+span){
                    //组内直接插入排序
                    int p = j-span;
                    Number temp = data[j];
                    while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
                        data[p+span] = data[p];
                        p -=span;
                    }
                    data[p + span] = temp;
                }
            }
            span=span/2;
        }


    }

    /**
     * 交换排序————冒泡排序
     *
     * @param data
     */
    public static void  冒泡排序(Number[] data)
    {
         for (int i = 0; i < data.length; i++) {
             //将相邻两个数进行比较，较大的数往后冒泡
             for (int j = 0; j < data.length - i-1; j++) {
                    if (data[j].doubleValue()> data[j + 1].doubleValue()) {
                           //交换相邻两个数
                           swap(data, j, j + 1);
                    }
             }
      }
    }
    /**
     * 交换排序————快速排序
     * @param data
     */
    public static void  快速排序(Number[] data)
    {
        QuickSort(data,0,data.length-1);
    }

     private static void QuickSort(Number[] data, int begin, int end) {
        // System.out.println(begin+":"+end);
         if(begin<end){
             //取中点
             int mid=(begin+end)/2;
             if(data[end].doubleValue()<data[begin].doubleValue()){
                 swap(data, end, begin);
             }
             if(data[end].doubleValue()<data[mid].doubleValue()){
                 swap(data, end, mid);
             }
             if(data[mid].doubleValue()<data[begin].doubleValue()){
                 swap(data, mid, begin);
             }

             swap(data, mid, begin);

            // System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );
            int min=begin+1;
            int big=end;

             while(true){
                while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}
                while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}
                if(min>=big){
                    break;
                }
                swap(data, min, big);
            }
             if(data[begin].doubleValue()>data[min].doubleValue()){
                 swap(data, begin, min);
             }

            if(min>1)
             QuickSort(data,begin,min-1);
            //if(min<end)
             QuickSort(data,min,end);
         }
    }
    /**
         * 选择排序————简单选择排序
         * @param data
         */
        public static void  简单选择排序(Number[] data)
        {
             for (int i = 0; i < data.length-1; i++) {
                 int smallPoint=i;
                 for (int j = i+1; j < data.length; j++) {
                        if (data[smallPoint].doubleValue()> data[j].doubleValue()) {
                            smallPoint=j;
                        }
                 }
                 swap(data, i, smallPoint);
          }

        }

         /**
         * 选择排序————堆排序
         * @param data
         */
        public static void  堆排序(Number[] data)
        {

             int n = data.length;
            for(int i=n/2;i>=0;i--){
                 keepHeap(data, n, i);
            }
              while (n > 0) {
                  swap(data, 0, n-1);
                  keepHeap(data, --n, 0);
              }
        }


         private static void keepHeap(Number[] a, int n, int i) {
             Number x = a[i];
              int j = 2 * i + 1;
              while (j <= n - 1) {
               if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())
                ++j;
               if (a[j].doubleValue() > x.doubleValue()) {
                a[i] = a[j];
                i = j;
                j = 2 * i ;
               } else{
                break;
                }
              }
              a[i] = x;
             }




         /**
             * 归并排序法————归并排序
             * @param data
             */
            public static void  归并排序(Number[] data)
            {
                 Number[] result = merge_sort(data,0,data.length-1);
                 for(int i=0;i<result.length;i++){
                     data[i]=result[i];
                 }
            }
         private static  Number[] merge_sort(Number[] array, int start, int end){
             Number[] result = new Number[end-start+1];
                if(start< end){
                    int mid= (start+end)/2;
                    Number[] left= merge_sort(array, start, mid);
                    Number[] right =  merge_sort(array, mid+1, end);
                   result= merge(left,right);
                } else if (start == end) {
                    result[0] = array[start];
                return result;
                }
                return result;
            }
           private static Number[]  merge(Number[] left, Number[] right) {
               Number[] result = new Number[left.length+right.length];
                int i=0;
                int j=0;
                int k=0;
                while(i< left.length&&j< right.length){
                    if(left[i].doubleValue()< right[j].doubleValue()){
                        result[k++] = left[i++];
                    }else{
                        result[k++] = right[j++];

                    }
                }
                while(i< left.length){
                    result[k++] = left[i++];
                }
                while (j< right.length) {
                   result[k++]= right[j++];
                }
                return result;
            }

           /**
            * 交换数组中指定的两元素的位置
            * @param data
            * @param x
            * @param y
            */
           private static void swap(Number[] data, int x, int y) {
               Number temp = data[x];
                  data[x] = data[y];
                  data[y] = temp;
           }
}