【数据结构排序】之一插入排序 所谓排序就是整理表中的元素，把给定的一组数据，使之按照关键字（一般为索引值）递增或递减的顺序进行排列。 2、排序的稳定性 在待排序的表格中，存在多个关键字相同的元素 ，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则这种排序方式是稳定的；反之不稳定。 3、插入排序 插入排序就是每次将一个待排序的元素，按其关键字的大小插入到已经排好序的子表中的适当位置，直到全部元素插入完整为止。 插入排序分为直接插入排序和希尔排序。 4、直接插入排序 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。 4.1 核心算法代码 ： 核心的代码：
1、排序的基本概念
所谓排序就是整理表中的元素，把给定的一组数据，使之按照关键字（一般为索引值）递增或递减的顺序进行排列。
2、排序的稳定性
在待排序的表格中，存在多个关键字相同的元素 ，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则这种排序方式是稳定的；反之不稳定。
3、插入排序
插入排序就是每次将一个待排序的元素，按其关键字的大小插入到已经排好序的子表中的适当位置，直到全部元素插入完整为止。
插入排序分为直接插入排序和希尔排序。
4、直接插入排序
直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
4.1 核心算法代码 ：
核心的代码：
1 /* 2 * 直接插入排序的核心程序 3 */ 4 void insertSort(int array[],arraylength) 5 { 6 int length =arraylength; 7 // 此循环从1开始，就是将0下标的元素当做一个参照 8 for (int i = 1; i < length; i++) 9 { 10 if (array[i] < array[i - 1])// 将当前下标的值与参照元素比较，如果小于就进入里面 11 12 { 13 14 int vacancy = i; // 用于记录比较过程中那个空缺出来的位置 15 16 int sentry = array[i]; // 设置哨兵，将当前下标对应的值赋给哨兵 17 // 这个循环很关键，从当前下标之前一个元素开始倒序遍历，比较结果如果比当前大的，就后移 18 for (int j = i - 1; j >= 0 && array[j] > sentry; j--) 19 { 20 vacancy = j; 21 array[j + 1] = array[j]; // 后移比当前元素大的元素 22 } 23 array[vacancy] = sentry; // 将哨兵，也就是当前下标对应的值置入空缺出来的位置 24 } 25 } 26 }
for (int i = 1; i < length; i++) { if (array[i] < array[i - 1]) { // 将当前下标的值与参照元素比较，如果小于就进入里面 int vacancy = i; // 用于记录比较过程中那个空缺出来的位置 int sentry = array[i]; // 设置哨兵，将当前下标对应的值赋给哨兵
@如果出列了，注意内部循环的条件，是从当前记录的前一个开始的，然后倒序遍历，条件是如果遍历过程中有大于sentry的记录，就后移记录array[j + 1] = array[j],然后将空缺位置变为j。
for (int j = i - 1; j >= 0 && array[j] > sentry; j--) { vacancy = j; array[j + 1] = array[j]; // 后移比当前元素大的元素 }
@比较完毕之后，array[vacancy] = sentry,是将出列的位置放到空缺位置。
array[vacancy] = sentry; // 将哨兵，也就是当前下标对应的值置入空缺出来的位置
4.2参考博文链接：
http://blog.csdn.net/ysjian_pingcx/article/details/8674454
http://blog.csdn.net/u014082714/article/details/43194827