本教程说明如何用Java编写插入排序程序。插入排序被认为是三种简单排序算法中最好的，另外两种简单排序算法是Bubble排序和Selection排序。尽管插入排序的时间复杂度也为O(n2)，但由于在大多数情况下交换次数较少且比选择排序快，因此它被认为比气泡排序快得多。

插入排序算法

插入排序基于"部分排序"的概念，在当前索引左侧的任何给定点元素都被视为已排序。请注意，这些元素被认为是相互排序的，因为它们尚未处于最终位置，这就是为什么使用术语"部分排序"的原因。任何剩余的元素(当前索引处的元素或者右边的剩余元素)可能必须插入到先前排序的元素之间，这将需要将这些元素向右移动以为插入的元素留出位置。

例如，如果当前索引在数组中为3，则索引0..2的元素将被视为在它们之间进行排序。
现在必须插入当前索引处的元素，因为最左边的元素意味着将索引0..2处的元素向右移动以为插入位置放置，从而使数组成为[1 3 5 7 12 10]

插入排序示例

这是一个长度为4的数组的示例，用于了解插入排序算法。假设传递的数组为[6，4，2，9]。

1在第一次迭代中，将索引1(即4)的元素与其左侧的元素6进行比较。由于4较小，因此必须将其插入索引0。要为其放置位置，必须将元素右移，这临时使数组为[6，6，2，9]，然后在第一次迭代后插入4以使数组为[4，6，2，9]。

2在第二次迭代中，将索引2的元素与其左侧的元素(索引1和0)进行比较。由于2小于6，所以发生移位使数组临时为[4、6、6、9]，因此2也小于4，因此再次发生移位使数组临时为[4、4、6、9]。在第二次迭代之后，现在插入2以使数组成为[2、4、6、9]。

3在第三次迭代中，将索引3的元素与其左侧的元素(索引2、1和0)进行比较。由于9大于所有元素，因此在此迭代中不需要交换。因此，排序后的数组为[2，4，6，9]。

插入排序Java程序

public class InsertionSort {
  public static void main(String[] args) {
    int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
    System.out.println("Original array- " + Arrays.toString(arr));
    int[] sortedArray = insertionSort(arr);      
    System.out.println("Sorted array- " + Arrays.toString(sortedArray));
  }
	
  private static int[] insertionSort(int[] arr){
    int j;
    for(int i = 1; i < arr.length; i++){
      int temp = arr[i];
      j = i;
      // from current index move left
      while(j > 0 && arr[j - 1] > temp){
        // shift elements to right
        arr[j] = arr[j - 1];
        --j;
      }
      // insert element at the new index position
      arr[j] = temp;
    }
    return arr;
  }
}

输出：

Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45]
Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]

插入排序空间和时间复杂度

如果我们发现算法在第一次迭代中最多需要1个比较，则在第二个迭代中，最后一个元素最多需要N-1个比较，因此比较的总数为N *(N-1)/ 2

因此，插入排序的平均和最坏情况下的时间复杂度为O(n2)。

插入排序是一种不需要辅助空间的就地排序算法，因此，插入排序的空间复杂度为O(1)。