一、算法原理

插入排序法：所謂插入排序法乃是將一個數(shù)目插入該占據(jù)的位置。

假設(shè)我們輸入的是 “53，27，36，15，69,  42” 我們從第二個數(shù)字開始，這個數(shù)字是27，我們的任務(wù)只要看看27有沒有正確的位置，我們的做法是和這個數(shù)字左邊的數(shù)字來比，因此我們比較27和53，27比53小，所以我們就交換27和53，原來的排列就變成了“27, 53, 36, 15, 69, 42 ”

接下來，我們看第3個數(shù)字有沒有在正確的位置。這個數(shù)字是36，它的左邊數(shù)字是53，36比53小，所以我們將36和53交換，排列變成了 “27,36, 53, 15, 69, 42 "我們必須繼續(xù)看36有沒有在正確的位置，36的左邊是27，27比36小，36就維持不動了,這時候排序還是“27, 36, 53, 15, 69, 42 "。

再來看第四個數(shù)字，這個數(shù)字是15，我們將15和它左邊的數(shù)字相比，都比15大，所以就將15一路往左移動，這時候排序變成了 “15, 27, 36, 53, 69, 42 ”。

再來看第五個數(shù)字，這個數(shù)字是69，我們將69和它左邊的數(shù)字相比，都比69小，所以就69維持不動了，這時候排序變成了 “15, 27, 36, 53, 69, 42 ”

最后，我們檢查第六個數(shù)字，這個數(shù)字是42，42必須往左移，一直移到42的左邊是36為止，所以我們的排列就變成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。

ps:讀者也可以自己打開下面的鏈接，自己設(shè)定要排序的數(shù)組，進行排序演練
直接插入排序動畫演示

所謂插入排序法，就是檢查第i個數(shù)字，如果在它的左邊的數(shù)字比它大，進行交換，這個動作一直繼續(xù)下去，直到這個數(shù)字的左邊數(shù)字比它還要小，就可以停止了。插入排序法主要的回圈有兩個變數(shù)：i和j，每一次執(zhí)行這個回圈，就會將第i個數(shù)字放到左邊恰當?shù)奈恢萌ァ?/p>

二、算法描述

1、從第一個元素開始，該元素可以認為已經(jīng)被排序。
2、取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描。
3、如果該元素（已排序）大于新元素，則將該元素移到下一位置。
4、重復(fù)步驟3，直到找到已排序的元素小于或者大于新元素的位置。
5、將新元素插入到該位置。
6、重復(fù)步驟2。

三、效率分析

如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況如下。
最好情況：序列已經(jīng)是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。
最壞情況：序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。
直接插入排序?qū)儆诜€(wěn)定的排序，最壞時間復(fù)雜度為O(n^2)，最好時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。
插入排序的賦值操作是比較操作的次數(shù)加上(n-1)次。
因此，插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用。

四、代碼實現(xiàn)

public class InsertSortTest { 
  public static void InsertSort(int[] source) { 
    int i, j; 
    int insertNode;// 要插入的數(shù)據(jù) 
    // 從數(shù)組的第二個元素開始循環(huán)將數(shù)組中的元素插入 
    for (i = 1; i < source.length; i++) { 
      // 設(shè)置數(shù)組中的第2個元素為第一次循環(huán)要插入的數(shù)據(jù) 
      insertNode = source[i]; 
      j = i - 1; 
      // 如果要插入的元素小于第j個元素，就將第j個元素向后移 
      while ((j >= 0) && insertNode < source[j]) { 
        source[j + 1] = source[j]; 
        j--;  
      } 
      // 直到要插入的元素不小于第j個元素,將insertNote插入到數(shù)組中 
      source[j + 1] = insertNode; 
      System.out.print("第" + i + "趟排序："); 
      printArray(source); 
    } 
  } 
 
  private static void printArray(int[] source) { 
    for (int i = 0; i < source.length; i++) { 
      System.out.print("\t" + source[i]); 
    } 
    System.out.println(); 
  } 
 
  public static void main(String[] args) { 
    int source[] = new int[] { 53, 27, 36, 15, 69, 42 }; 
    System.out.print("初始關(guān)鍵字："); 
    printArray(source); 
    System.out.println(""); 
    InsertSort(source); 
 
    System.out.print("\n\n排序后結(jié)果："); 
    printArray(source); 
  } 
 
} 

五、運行結(jié)果

初始關(guān)鍵字：   53 27 36 15 69 42 
 
第1趟排序： 27 53 36 15 69 42 
第2趟排序： 27 36 53 15 69 42 
第3趟排序： 15 27 36 53 69 42 
第4趟排序： 15 27 36 53 69 42 
第5趟排序： 15 27 36 42 53 69 
 
 
排序后結(jié)果： 15 27 36 42 53 69 

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論