【插入排序算法】初學算法之排序--直接插入排序

前言：

　　厚厚一本《算法第四版》，看到五分之一就已經收益良多，而前五分之一又大部分是關于排序，有冒泡排序、快速排序、堆排序、直接插入排序、希爾排序等等，了解起來也不算特别的難，今天就跟大家分享其中的一種 —— 直接插入排序算法，這裡我實作了javascript和java兩個語言版本。

思路：

　　在生活中，如果我們要對撲克牌按大小排序，我們會怎麼排呢？ 

　　　　① 首先找出一張牌 放在桌子上

　　　　② 拿出第二張牌，比第一張小就放上面，比第一張大就放下面

　　　　③ 拿出第三張牌，比第一張小就放上面，比第一張大就和第二張對比 ，比第二張小放上面，比第二長大再和下一張對比......

　　　　④ 重複步驟 最終撲克牌排序就完成了

　　從這三個步驟我們可以得出一些結論

　　　　① 放在桌子上的牌，總是有序的。

　　　　② 拿出的牌與前一張對比 直到遇到比那張小的 就放在上面 

實作：

　　直接插入排序要點 ： 每步将一個待排序的對象,按其排序碼大小,插入到前面已經排好序的一組對象的适當位置上,直到對象全部插入為止。

更清楚一點說： 将目前排序的數組元素，放到前面已經有序的元素的适當位置，循環到全部有序為止；

　　　javascript實作：

　　　　　　

function insertSort(arr){
                for(var i = 1;i<arr.length;i++){
                    var temp = arr[i];  //待排序元素
                    var j = i;
                    while(j>0){   
                        if( temp < arr[j-1] ){ //如果前一個數比它自己大 
                            var a = arr[j-1];                //交換它和它前一個元素
                                arr[j-1] = arr[j];
                                arr[j] = a;            
                                j--;        //交換了j  j的位置--
                        }else{
                            j=0; //當找到比它小的數 則結束這次排序 
                        }
                    }
                }
                return arr;
            }      

當輸入 數組 [6,1,2,7,9,3,4,5,10,8,8,9] 時，得到的結果是 [1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10]

再分析一下while中的步驟:

　　

function insertSort(arr){
               //arr = [6,1,2,7,9,3,4,5,10,8,8,9]
                for(var i = 1;i<arr.length;i++){
                    var temp = arr[i];  // 例如i=1的話  temp = arr[1];
                    var j = i;                
                    while(j>0){   
                        if( temp < arr[j-1] ){ // 1 < 6  等于 true
                            var a = arr[j-1];                
                                arr[j-1] = arr[j];
                                arr[j] = a;            //交換1 - 6
                                j--;        //i--  i=0 結束本次循環  這時候 arr = [1,6,2,7....] 再找到2 依次循環 
                        }else{
                            j=0; 
                        }
                    }
                }
                return arr;
            }      

java的實作：

public class SortUtil {
    //直接插入排序算法
    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){
            Comparable tem = a[i];  //待排序元素
            int j = i;
            
            while(j>0){
                if(less(tem,a[j-1])){　　//less比較元素 tem比前一個小的話 
                    exch(a,j,j-1);
                    j--;
                }else{
                    j=0;
                }
            }
        }
    }
   /*
     * compareTo 比較方法
     * @param {Comparable} v 如果v小于w  傳回true
     * @param {Comparable} w 如果v大于等于w  傳回false
     * @return {boolean} 傳回比較的值
     *      * */
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }
    /*
     * compareTo 交換元素
     * @param {Comparable[]} a 要交換的可排序數組
     * @param {int} i 交換1下标
     * @param {int} j 交換2下标
     *      * */
    public static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static void show(Comparable[] a){
        for(int i=0;i<a.length;i++){
            StdOut.print(a[i]+" ");
            StdOut.println();
        }
    }
    /*
     * compareTo 測試元素是否有序
     * @param {Comparable[]} a 可排序數組
     * @return {boolean} 是否是有序數組 
     * * */
    public static boolean isSorted(Comparable[] a){
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i-1])){
                return false;
            }
        }
        return true;
    }
    /*
     * compareTo 将int[]轉換成Integer[] 
     * @param {int[]} a int數組
     * @return {Integer[]} 轉換後的Integer[] 
     * * */
    public static Integer[] intTo(int[] a){
        Integer[] con = new Integer[a.length];
            for(int i=0;i<a.length;i++){
                con[i] = new Integer(a[i]);
            }
        return con;
    }
    //main
        public static void main(String[] args){
            Integer[] a = intTo(In.readInts(args[0]));
            runTime runtime = new runTime();
            sort(a);
            if(!isSorted(a)){StdOut.println("sort is error");System.exit(0);};
            StdOut.println(runtime.End());
        }
}      

總結：

　　① 抓住要點，每步将一個待排序的對象,按其排序碼大小,插入到前面已經排好序的一組對象的适當位置上,直到對象全部插入為止。

　　② 學習時進行步驟分析，将數組按邏輯的方式人工排序一次，分析它的步驟，最終轉化成代碼實作 

　　直接插入排序算法是希爾排序的基礎方法，算法的大門前總有走不完的階梯，隻有堅持不懈、努力學習，才能登高而望，一覽衆山小。

========================================================

轉載請注明出處。