排序算法java版(转载)

转载自 ---- http://yiyickf.iteye.com/blog/1047010

 

先推荐一篇关于排序算法的文章：http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

本文思路部分来源于上篇文章，但测得的结果似乎不大相同，不知是因为java的缘故还是因为我算法的缘故，欢迎拍砖。

 

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

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;
           }
}