午后星期午
          

          

          




          
	
					
	
          
		
          
			java 插入排序
		
          
		不扯太多概念性的東西，簡單點來說，插入排序 將數組所有元素劃分成了有序區和無序區，假設當前數組有 N 個元素，
          開始默認第一個元素（下標為0）所處的位置是有序區，這是局部有序，從第二個元素（i=1）至數組最后一個元素（i=N-1）屬于無序區；
          假設數組元素是按從左至右存放的，如果用 i 來標記無序區中的第一個元素下標，也就是無序區中最左邊或者說是無序區中下標值最小的下標，
          則每趟排序是將下標 i 所指向的有效值插入有序區的適當位置，使得每趟排序完成之后，有序區的所有元素總是保持局部有序狀態。
          按這樣來回 N -1 趟插入之后，則 N 個元素已成有序狀態。

          盡管插入排序的復雜度也是 O(n^2)，但一般情況下，插入排序會比冒泡排序快一倍，要比選擇排序還要快一點。


          排序基類：BaseSort.java
          


          package sort;
          /**
           * -----------------------------------------
           * @文件: BaseSort.java
           * @作者: fancy
           * @郵箱: fancydeepin@yeah.net
           * @時間: 2012-7-18
           * @描述: 基類
           * -----------------------------------------
                     */
          public class BaseSort {

                        protected final static int ASC  = 1;       // 升序
              protected final static int DESC = 0;    // 降序
              
                        //交換i1、i2下標指向的值
              public void swap(Object[] array, int i1, int i2){
                  Object tempObj;
                  tempObj            = array[i1];
                  array[i1]           = array[i2];
                  array[i2]           = tempObj;
                  tempObj           = null;
              }
              
                        //打印輸出數組元素
              public void print(Object[] array){
                            for(Object obj : array){
                      System.out.print(obj           + "    ");
                  }
                  System.out.println();
              }
          }


          插入排序：InsertSort.java
          


          package sort;
          /**
           * -----------------------------------------
           * @文件: InsertSort.java
           * @作者: fancy
           * @郵箱: fancydeepin@yeah.net
           * @時間: 2012-7-18
           * @描述: 插入排序
           * -----------------------------------------
                     */
          public class InsertSort extends BaseSort{
              
                        /**
               * @方法名:    insertSort 
               * @參數名： array 排序對象
               * @參數名： order 排序順序
               * @描述語:    插入排序:默認第一個是有序,使其余的像紙牌游戲那樣依次插入，復雜度 O(n^2)
                         */
                        public void insertSort(Object[] array, int order){
                            int length = array.length;
                            if(order == ASC){
                                for(int i = 1, j; i < length; i++){ //默認第1個(下標0)有序，i是無序區第一個元素下標，第i趟結束后，i下移，如此來回 N -1趟
                          for(j = 0; j < i; j++){       //將無序區下標為i所指向的值插入有序區適當位置
                              if(Double.parseDouble(array[j].toString()) > Double.parseDouble(array[i].toString())){
                                  swap(array, i, j);
                              }
                          }
                          System.out.println(          "--------------------------------------------------------------------------->第" + i + "趟");
                          print(array);
                      }
                  }          else if(order == DESC){
                                for(int i = 1, j; i < length; i++){ //默認第1個(下標0)有序，i是無序區第一個元素下標，第i趟結束后，i下移，如此來回 N -1趟
                          for(j = 0; j < i; j++){       //將無序區下標為i所指向的值插入有序區適當位置
                              if(Double.parseDouble(array[j].toString()) < Double.parseDouble(array[i].toString())){
                                  swap(array, i, j);
                              }
                          }
                          System.out.println(          "--------------------------------------------------------------------------->第" + i + "趟");
                          print(array);
                      }
                  }
              }
          }


          如需了解上面由粉紅色標記出來的代碼的用意，請參考我 java 分類里的 冒泡排序 這一隨筆 ： http://www.aygfsteel.com/fancydeepin/archive/2012/07/18/java_bubblesort.html


          測試類：TestApp.java
          


          package sort;
          /**
           * -----------------------------------------
           * @文件: TestApp.java
           * @作者: fancy
           * @郵箱: fancydeepin@yeah.net
           * @時間: 2012-7-18
           * @描述: 測試類
           * -----------------------------------------
                     */
          public class TestApp {

                        public static void main(String[] args) {
                  Object[] array           = {9,5,7,1,6,3,8,10,4,2};
                  (          new InsertSort()).insertSort(array, InsertSort.ASC);
              }
          }


          后臺輸出打印結果：

          


          --------------------------------------------------------------------------->第1趟
          5    9    7    1    6    3    8    10    4    2    
          --------------------------------------------------------------------------->第2趟
          5    7    9    1    6    3    8    10    4    2    
          --------------------------------------------------------------------------->第3趟
          1    5    7    9    6    3    8    10    4    2    
          --------------------------------------------------------------------------->第4趟
          1    5    6    7    9    3    8    10    4    2    
          --------------------------------------------------------------------------->第5趟
          1    3    5    6    7    9    8    10    4    2    
          --------------------------------------------------------------------------->第6趟
          1    3    5    6    7    8    9    10    4    2    
          --------------------------------------------------------------------------->第7趟
          1    3    5    6    7    8    9    10    4    2    
          --------------------------------------------------------------------------->第8趟
          1    3    4    5    6    7    8    9    10    2    
          --------------------------------------------------------------------------->第9趟
          1    2    3    4    5    6    7    8    9    10



             [ 轉載出處：http://www.aygfsteel.com/fancydeepin ]           
          
		
          
			posted on 2013-12-31 13:49 午后星期午 閱讀(82) 評論(0)  編輯  收藏  所屬分類: Java 
		
          
	
          
	
	





          
	    
    




          








          

				

          



    







          
        
	




主站蜘蛛池模板：
雅江县|
萨嘎县|
冕宁县|
揭西县|
大余县|
武陟县|
通化县|
昭苏县|
怀仁县|
广元市|
合作市|
读书|
宁夏|
吉首市|
瓮安县|
怀柔区|
大兴区|
深水埗区|
石屏县|
建水县|
潢川县|
彝良县|
清远市|
白山市|
达孜县|
桑植县|
乌兰察布市|
马鞍山市|
奉化市|
曲靖市|
宝应县|
察雅县|
常山县|
金川县|
平泉县|
博爱县|
永顺县|
富宁县|
合水县|
囊谦县|
平谷区|