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]