插入排序 Insertion sort

2015/06/04 17:27
阅读数 2
是一种简单的排序方法。时间复杂度为   O(n^2),即N的平方。在数据量较小的情况下,是比较有效的排序方式。

输入:N个数 < a1,a2,a3.....an >
输出:输入序列的一个排序 <a'1,a'2,a'3.....a'n> 要求 a'1<=a'2<=.....a'n

思想:把序列分为2部分:已排序,未排序。 每次从未排序中取一个数,与已排序中的值比较,插入到合适的位置。

public   class   InsertSort {
       public   static   void   main(String[] args) {
               //   TODO   Auto-generated method stub
               int [] a;
            a =   new   int [30];
            Random rand =   new   Random();
               for (   int   i=0;i<a.   length ;i++){
                  a[i] = rand.nextInt(100);
            }
             println(a);
               long   s = System. nanoTime();
               int [] b= sort(a);
               long   dur = System. nanoTime() - s;         
             println(b);
            System.   out .println(dur);            
      }
      
       public   static   int [] sort( int [] a){
               for (   int   i=1;i<a.   length ;i++){
                     int   key = a[i];
                     int   j=i-1;
                     while   (j>=0 && a[j]>key){
                        a[j+1] = a[j];
                        j=j-1;
                  }
                  a[j+1] = key;
            }
               return   a;         
      }

       public   static   void   println( int [] a){
            System.   out .print(   "[" );
               for   (   int   i = 0; i < a.   length ; i++) {
                  System.   out .print(a[i]);
                     if (i != a.   length -1)
                        System.   out .print(   "," );
            }
            System.   out .println(   "]" );
      }
}


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部