中心思想

每次选择一个元素K插入到之前【已排好序】的部分A[1~i]中，插入过程中K依次由后向前与A[1~i]中的元素进行比较。若发现A[x] >= K,则将K插入到A[x]的后面，插入前需要移动元素。

代码实现

public int[] sort(int[] sourceArray) {
  		// 选择数组中第二个元素,插入到之前已排序好的数组中.
  		for (int i = 1; i < sourceArray.length; i++) {
        		int temp = sourceArray[i];
        		// 从已经排序的序列最右边的开始比较，找到比其小的数
        		int j = i - 1;
        		// 遍历条件的定义: 最右边(即要插入元素的前一位) ~ 最左边(0) 判断条件的定义:要插入的元素与已排好序的元素一一比较大小
        		while (j >= 0 && temp < sourceArray[j]) {
              		// 如果 要插入的元素比当前比较的元素小 ==> 将被比较的数 统统往后移
            			sourceArray[j + 1] = sourceArray[j];
              		j--;
            }
        		
        		if (j != i - 1) {
              		// 如果 j 发生变化(一定不等于 i)，把要插入的数 插入到 j 停止 循环的时候
              		sourceArray[j + 1] = temp;
            }
      }
  		return sourceArray;
}

时间复杂度

1. 最好的情况：正序有序（从小到大），这样只需要比较n次，不需要移动，因此时间复杂度为 O（n）。
2. 最坏的情况：逆序有序（从大到小），这样每一个元素就需要比较n次，共有n个元素，因此复杂度为 O（n^2）。

稳定性

稳定性 ，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时序规有多个排则的情况下。在插入排序中，K1 是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面（没有必要查到K1的前面，这样做还需要移动一次！！），因此，插入排序是稳定的。