介绍：
插人排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。如图2-1所示，拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。对于少量元素的排序，插入排序是一个有效的算法。
思想：
首先我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，然后在未排序区间中依次取出元素并插入到已排序区间的合适位置，并保证已排序区间一直是有序。重复这个步骤直到未排序区间元素为空，排序完成。
复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
代码实现：
// Java代码 class StraighInsertionSort { public static void insertionSort(int[] array) { int length = array.length;// 记录数组长度 for (int i = 1; i < length; ++i) {// 遍历无序序列 int key = array[i];// 记录准备插入的元素 int j = i - 1;// 记录当前比较位置指针 while (j >= 0 && array[j] > key) {// 寻找插入位置 array[j + 1] = array[j];// 元素后移 --j;// 指针减1，当前比较位置前移 } array[j + 1] = key;// 插入合适位置 } } }
// C++代码 class StraightInsertionSort { public: static void insertionSort(int array[], int length) { for (int i = 1; i < length; ++i) {// 遍历无序序列 int key = array[i];// 记录准备插入的元素 int j = i - 1;// 记录当前比较位置指针 while (j >= 0 && array[j] > key) {// 寻找插入位置 array[j + 1] = array[j];// 元素后移 --j;// 指针减1，当前比较位置前移 } array[j + 1] = key;// 插入合适位置 } } };
直接插入排序(Straight Insertion Sort)
原文：https://www.cnblogs.com/Acx7/p/14608953.html