基本思想
插入排序(InsertionSorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始有序表只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
时间复杂度
在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为插入排序 - 图1 。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为插入排序 - 图2 。
平均来说，A[1..j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是输入规模的二次函数

注意：

每次处理就是将无序的数列中第一个元素与有序数列的元素从后到前比较，找到插入位置，将该元素插入到有序数列的适当的最终的位置上（稳定排序）。
代码示例

  1. /**
  2. * 推荐使用
  3. * @param arr
  4. */
  5. public static void sortTest1(int[] arr) {
  6.         if (arr == null || arr.length < 2) return;
  7.         for (int i = 1; i < arr.length; i++) {
  8.             int insertValue = arr[i];
  9.             int insertIndex = i - 1;
  10.             while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
  11.                 arr[insertIndex + 1] = arr[insertIndex];
  12.                 insertIndex--;
  13.             }
  14.             arr[insertIndex + 1] = insertValue;
  16.         }
  17.     }
  18. /**
  19. * 双重for循环效率低下
  20. * @param arr
  21. */
  22.     public static void sortTest2(int[] arr) {
  23.         if (arr == null || arr.length < 2) return;
  24.         for (int i = 0; i < arr.length; i++) {
  25.             for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
  26.                 arr[j] = arr[j] ^ arr[j - 1];
  27.                 arr[j - 1] = arr[j] ^ arr[j - 1];
  28.                 arr[j] = arr[j] ^ arr[j - 1];
  29.             }
  30.         }
  31.     }
  33.     public static void sortTest3(int[] arr) {
  34.         if (arr == null || arr.length < 2) return;
  35.         for (int i = 0; i < arr.length; i++) {
  36.             for (int j = i; j > 0; j--) {
  37.                 if (arr[j]<arr[j-1]){
  38.                     arr[j] = arr[j] ^ arr[j - 1];
  39.                     arr[j - 1] = arr[j] ^ arr[j - 1];
  40.                     arr[j] = arr[j] ^ arr[j - 1];
  41.                 }
  42.             }
  43.         }
  44.     }