排序算法之直接插入排序（JAVA）

插入排序的思想：每次讲一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到所有记录全部插入完成。

直接插入排序：我们可以将数组的第一个元素看做已经排好序的子序列，这样从数组的第二个元素开始遍历，依次向排好序的子序列做插入排序操作。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：每次插入元素时，都是从后向前比较移动，不会出现相同元素相对位置发生变化，所以直接插入排序是稳定的排序。
  补充：当数组中的元素全部有序时，每次插入操作都只需要比较一次而不移动元素，此时时间复杂度为O(n).

直接插入排序的第一种实现：

//2, 5, 1, 3, 6
    //升序插入
    public void insertSort1(int[] a, int n) {
        int i,j;
        //从数组的第二个元素开始遍历
        for(i=1; i<n; i++) {

            //为a[i]在前面的a[0...i-1]中找一个合适的位置
            //因为a[0..i-1]有序，所以第一次碰见比a[i]小的a[j]时，a[i]的位置就是在a[j]之后
            for(j=i-1; j>=0; j--) {
                if(a[j] < a[i])
                    break;
            }

            //找到了合适的位置
            if(j != i-1) {
                //将j到i之间比a[i]大的数都后移
                int temp = a[i];
                int k;
                for(k=i-1; k>j; k--) {
                    a[k+1] = a[k];
                }
                a[k+1] = temp;
            }
        }

        System.out.print(Arrays.toString(a));
    }

仔细观察上述代码，我们可以看到第一层for循环内部的for循环和if是可以合并的。
如下：

public void InsertSort2(int[] a, int n) {
        int i, j, k;
        for(i=1; i<n; i++) {
            //当a[0..i-1]是升序的，所以有序序列的最大值就是a[i-1]
            if(a[i] < a[i-1]) {

                int temp = a[i];

                for(j=i-1; j>=0 && a[j] >temp; j--) {
                    a[j+1] = a[j];
                }

                a[j+1] = temp;
            }
        }
        System.out.println(Arrays.toString(a));
    }

给出测试实例及代码：

public static void main(String[] args) {
        int[] a = new int[]{2,5,1,3,6};
        InsertSort is = new InsertSort();

        is.insertSort1(a, a.length);
        is.InsertSort2(a, a.length);
    }