Java 資料結構 - 插入排序

這是一種基於比較的原地排序演算法。這裡維護一個始終排序的子列表。例如，保持陣列的下半部分已排序。要插入到此已排序子列表中的元素必須找到其適當的位置，然後插入到該位置。因此得名插入排序。

順序搜尋陣列，並將未排序的項移動並插入到已排序的子列表（在同一陣列中）。此演算法不適用於大型資料集，因為其平均和最壞情況下的複雜度為 Ο(n2)，其中 n 是項數。

演算法

Step 1: If it is the first element, it is already sorted. return 1;
Step 2: Pick next element.
Step 3: Compare with all elements in the sorted sub-list.
Step 4: Shift all the elements in the sorted sub-list that is greater than the value to be sorted.
Step 5: Insert the value.
Step 6: Repeat until list is sorted.

示例

import java.util.Arrays;

public class InsertionSort {
   public static void main(String args[]) {
      int myArray[] =  {10, 20, 25, 63, 96, 57};
      int size = myArray.length;
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));
      
      for (int i = 1 ;i< size; i++) {
         int val = myArray[i];  
         int pos = i;
         
         while(myArray[pos-1]>val && pos>0) {
            myArray[pos] = myArray[pos-1];
            pos = pos-1;
         }
         myArray[pos] = val;
      }
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));	  
   }
}

輸出

Contents of the array before sorting : 
[10, 20, 25, 63, 96, 57]
Contents of the array after sorting : 
[10, 20, 25, 57, 63, 96]