Java排序之InsertionSort插入排序的實例

插入排序 の implementation

---

############################################# # ##　　插入排序就像打賭的時候，例如雙扣。抽牌的時候，一次拿一張牌，這張牌和之前的牌一張張比較。選擇把這張牌插入什麼位置，排好順序的位置後打牌更順。要不然得一個一個找到時麻煩。也不利於打牌的大局觀。看下圖##################　　假設第一次抽到梅花7， 不用排序。因為只有一張#####################　　接著抽到梅花10 ###。因為10比7大，所以不用排序。 ##################　　再接著抽卡。發現抽到了梅花5 ###。這時候不要猶豫，2點真的不算大的。果斷棄牌##################　　接著我們拿 5 和 10 比較。 5 小於 10 所以交換位置。 #####################　　拿5再和7比。 5 比 7 小。 所以交換 5 和 7 的位置 得到###。 ##################　　這個時候就已經是sorted的了。 原理就是這樣子。 ##################　　因為比較簡單。直接貼上程式碼#########

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort

######################效能分析######　　最壞的情況就是每次抽到的卡是最小的。這時候每次都需要從尾部遍歷到頭部。時間是N ^ 2成正比######　　最好的情況就是已經排好序了。因為已經排好序了。所以每次抽到的牌都不需要排序。 時間是 N 成正比############

以上是Java排序之InsertionSort插入排序的實例的詳細內容。更多資訊請關注PHP中文網其他相關文章！