使用Java編寫一個插入排序算法

使用Java編寫一個插入排序算法？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

一、算法原理

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

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

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

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

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

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

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

所謂插入排序法，就是檢查第i個數字，如果在它的左邊的數字比它大，進行交換，這個動作一直繼續下去，直到這個數字的左邊數字比它還要小，就可以停止了。插入排序法主要的回圈有兩個變數：i和j，每一次執行這個回圈，就會將第i個數字放到左邊恰當的位置去。

二、算法描述

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

三、效率分析

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

四、代碼實現

public class InsertSortTest { 
  public static void InsertSort(int[] source) { 
    int i, j; 
    int insertNode;// 要插入的數據 
    // 從數組的第二個元素開始循環將數組中的元素插入 
    for (i = 1; i < source.length; i++) { 
      // 設置數組中的第2個元素為第一次循環要插入的數據 
      insertNode = source[i]; 
      j = i - 1; 
      // 如果要插入的元素小于第j個元素，就將第j個元素向后移 
      while ((j >= 0) && insertNode < source[j]) { 
        source[j + 1] = source[j]; 
        j--;  
      } 
      // 直到要插入的元素不小于第j個元素,將insertNote插入到數組中 
      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("初始關鍵字："); 
    printArray(source); 
    System.out.println(""); 
    InsertSort(source); 
 
    System.out.print("\n\n排序后結果："); 
    printArray(source); 
  } 
 
} 

五、運行結果

初始關鍵字：   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 
 
 
排序后結果： 15 27 36 42 53 69 

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。