排序算法（一）直接插入排序算法

1.基本概念
  直接插入排序（Straight-Insertion-Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
  通俗一点的讲，就是把数组中的元素一个个取出来，每取出一个就组成一个有序列表，直到将元素取完为止。例如：[20, 9, 14, 15, 30]这样一个数组，以升序为例，取第一个数时，组成有序列表20；取第二个数时，组成有序列表9,20；取第三个数时，组成9,14,20；取第四个数时，组成9,14,15,20；依次类推至取完元素为止。
2.过程图片

public class InsertionSort {

    public static void main(String[] args) {
        int[] num = new InsertionSort().sortNum();
        for (int n : num) {
            System.out.print(n + " ");
        }
    }

    public int[] sortNum() {
        int numbers[] = {20, 9, 14, 15, 30};
        int length = numbers.length; // 数组的长度
        int cur; // 记录欲插入的数
        int j; // 记录与欲插入数作比较的数的下标

        for (int i = 1; i < length; i++) {
            cur = numbers[i];
            j = i - 1;
            while (j >= 0 && numbers[j] < cur) { // 从后面往前面循环作比较
                numbers[j+1] = numbers[j];
                j--;
            }
            numbers[j+1] = cur; // 将欲插入数插入到对应额的位置
        }

        return numbers;
    }
}

4.过程解说
上述代码为例，for循环的次数即是要插入的数的数目（如上代码循环4次），过程如下：

• 第一次循环：
    此时i=1、cur=9、j=0。while条件不成立，退出while循环，最后numbers[j+1] = cur对结果也无影响。数组依然是[20, 9, 14, 15, 30]。
• 第二次循环：
    此时i=2、cur=14、j=1，while条件第一次成立，将numbers[j]=numbers[1]=9往后挪一位，数组是[20, 9, 9, 15, 30]，j减一。
    此时i=2、cur=14、j=0，while条件不成立，退出while循环，最后一步将欲插入数cur=14插入到numbers[j+1]=numbers[1]位。最终数组是[20, 14, 9, 15, 30]。
• 第三次循环：
    此时i=3、cur=15、j=2，while条件第一次成立，将numbers[j]=numbers[2]=9往后挪一位，数组是[20, 14, 9, 9, 30]，j减一。
    此时i=3、cue=15、j=1，while条件第二次成立，将numbers[j]=numbers[1]=14往后挪一位，数组是[20, 14, 14, 9, 30]，j减一。
    此时i=3、cur=15、j=0，while条件不成立，退出while循环，最后一步将欲插入数cur=15插入到numbers[j+1]=numbers[1]位。最终数组是[20, 15, 14, 9, 30]。
• 第四次循环：
    此时i=4、cur=30、j=3，while条件第一次成立，将numbers[j]=numbers[3]=9往后挪一位，数组是[20, 15, 14, 9, 9]，j减一。
    此时i=4、cur=30、j=2，while条件第二次成立，将numbers[j]=numbers[2]=14往后挪一位，数组是[20, 15, 14, 14, 9]，j减一。
    此时i=4、cur=30、j=1，while条件第三次成立，将numbers[j]=numbers[1]=15往后挪一位，数组是[20, 15, 15, 14, 9]，j减一。
    此时i=4、cur=30、j=0，while条件第四次成立，将numbers[j]=numbers[0]=20往后挪一位，数组是[20, 20, 15, 14, 9]，j减一。
    此时i=4、cur=30、j=-1，while条件不成立，退出while循环，最后一步将欲插入数cur=30插入到numbers[j+1]=numbers[0]位。最终数组是[30, 20, 15, 14, 9]。
  5.算法复杂度（参考维基百科）

• 时间复杂度

  • 最好情况，序列是升序排列，在这种情况下，只需进行 n-1 比较，即Tbest(n)=O(n)
  • 最坏情况，序列是降序排列，那么此时需要进行的比较共有 1/2n(n-1)次，即Tworse(n)=O(n^2)
  • 平均情况，为 Tavg(n)=O(n2)。

• 空间复杂度

  • 由程序很容易得 S(n)=O(1)。

直接插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如量级小于千，那么直接插入排序还是一个不错的选择，因此在 STL 的 sort 算法和 stdlib 的 qsort 算法中，都将直接插入排序作为快速排序的补充，用于少量元素的排序（通常为 8 个或以下）。