直接插入排序应用了插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

直接插入排序算法的基本思想：

　　在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

1．简单方法

    　首先在当前有序区arr[0..i-1]中查找arr[i]的正确插入位置j(0≤j≤i-1)；然后将arr[j．．i-1]中的记录均后移一个位置，腾出j位置上的空间插入arr[i]。

  注意：

    　若arr[i]的关键字大于等于arr[0．．i-1]中所有记录的关键字，arr[i]就是插入原位置。

2．改进的方法

　　一种查找比较操作和记录移动操作交替地进行的方法。

具体做法：

    　将待插入记录arr[i]的关键字从右向左依次与有序区中记录arr[j](j=i-1，i-2，…，0)的关键字进行比较：

    　① 若arr[j]的关键字大于arr[i]的关键字，则将arr[j]后移一个位置；

        ② 若arr[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为arr[i]的插入位置。

 

1 package com.bingoogol.algorithm.sort; 2  3 /** 4  * 直接插入排序 5  *  6  * @author bingoogol@sina.com 7  */ 8 public class InsertSort { 9 10     public static void main(String[] args) {11         int[] arr = new int[] { 2, 6, 30, 25, 9, 18, 13 };12         System.out.print("排序前：");13         InsertSort.printArr(arr);14         InsertSort.sort(arr);15         System.out.print("排序后：");16         InsertSort.printArr(arr);17     }18 19     public static void sort(int[] arr) {20         for (int i = 1; i < arr.length; i++) {21             int temp = arr[i];22             int j = i - 1;23             while (j >= 0 && arr[j] > temp) {24                 arr[j + 1] = arr[j];25                 j--;26             }27             arr[j + 1] = temp;28         }29     }30 31     public static void swap(int[] data, int i, int j) {32         int temp = data[i];33         data[i] = data[j];34         data[j] = temp;35     }36 37     public static void printArr(int[] arr) {38         for (int i = 0; i < arr.length - 1; i++) {39             System.out.print(arr[i] + ",");40         }41         System.out.println(arr[arr.length - 1]);42     }43 }