特别说明：
对于算法，重在理解其思想、解决问题的方法，思路。因此，以下内容全都假定待排序序列的存储结构为：顺序存储结构。
一：插入排序算法思想
01.设待排序序列为 。插入排序将
划分为由已排序好序的
部分 以及 未排序的
部分组成；
注意：刚开始时 部分其实可认为只有一个元素，即：
元素
02.排序开始时，每次从 序列中(随机，但一般是直接取第一个元素)取出一个元素
，将其插入到已排好序
部分的"适当位置
"，使得以下条件成立：
，{ 1
x
i
y
m }
03.将位置 及其后的所有元素全部后移一个位置后，赋值
=
即可；
04.重复执行第 02、03 步骤，直到未排序部分为空为止；
二：直接插入排序算法
直接插入排序是严格按照前面思想设计的一种插入排序算法。因此，其编码实现参考如下：
1 // 2 // summary : 直接插入排序 3 // in param : seqlist 待排序列表.同时也是排完序列表. 4 // in param : nLen 列表长度 5 // out param : -- 6 // return : -- 7 // !!!note : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效. 8 // 02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的. 9 void insert_sort(int seqlist[/*nLen*/], const int nLen) { 10 auto nTemp = 0; 11 auto nInnerIdx = 0; 12 for (auto nOuterIdx = 1; nOuterIdx < nLen; ++nOuterIdx) { 13 nTemp = seqlist[nOuterIdx]; 14 for (nInnerIdx = nOuterIdx; nInnerIdx > 0; --nInnerIdx) { 15 if (nTemp >= seqlist[nInnerIdx - 1]) { 16 break; 17 } 18 seqlist[nInnerIdx] = seqlist[nInnerIdx - 1]; 19 20 } 21 seqlist[nInnerIdx] = nTemp; 22 } 23 }
直接插入排序算法的辅助空间复杂度 ；算法是稳定的；属于原地排序算法；平均时间复杂度
；每一趟的平均数据移动次数为
次；每一趟的平均数据比较次数为
次。
三：折半插入排序算法
从前文内容可知，为得知适当的位置 ，需要从
位置一直往前逐一比较元素，这样(每一趟的)平均比较次数是线性的(为
次)。但由于这前
个元素已经明确是有序的，因此利用这一有利条件，可以利用折半查找在
次数内定位到
位置。因此，折半插入排序算法，算是对直接插入排序的一种改进。算法编码参考如下：
1 // 2 // summary : 折半插入排序 3 // in param : seqlist 待排序列表.同时也是排完序列表. 4 // in param : nLen 列表长度 5 // out param : -- 6 // return : -- 7 // !!!note : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效. 8 // 02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的. 9 void binary_insert_sort(int seqlist[/*nLen*/], const int nLen) { 10 auto nTemp = 0; 11 auto nInnerIdx = 0; 12 auto nLow = 0; 13 auto nHigh = 0; 14 auto nMid = 0; 15 for (auto nOuterIdx = 1; nOuterIdx < nLen; ++nOuterIdx) { 16 nTemp = seqlist[nOuterIdx]; 17 18 nLow = 0; 19 nHigh = nOuterIdx; 20 while (nLow < nHigh) { 21 nMid = (nLow + nHigh) >> 1; 22 nTemp < seqlist[nMid] ? nHigh = nMid : nLow = nMid + 1; 23 } 24 for (nInnerIdx = nOuterIdx; nInnerIdx > nHigh; --nInnerIdx) { 25 seqlist[nInnerIdx] = seqlist[nInnerIdx - 1]; 26 } 27 seqlist[nInnerIdx] = nTemp; 28 } 29 }
折半插入排序算法总体情况与直接插入排序是一样的，只是比较次数总体上会优于直接插入排序。算法实现上，会稍稍比直接插入排序复杂些。
四：2路插入排序算法
相比于排序元素的"关键字"比较而言，多数情况下数据的移动可能会更加的耗时些(因为现实应用中的数据可能就不止是简简单单的基础数据类型，有时候可能还是复杂的自定义类型对象)。2路插入排序算法利用额外的辅助空间，以求尽量减少直接插入排序的数据移动次数。注意：虽说移动次数会得到改善，但付出的代价也是较大的，其需要的额外辅助空间与待排序序列的空间一样大小，因此，如果在某些空间资源较为缺乏的应用场合，该算法就不太可行。
2路插入排序算法的思想：
假设待排序序列为 ，辅助序列为
01.将 的第一个元素赋值给
的第一个元素。即：
=
；
02.从 中取出下一个元素
，将其与
比较。当比
小时，则插入到
的"低端"的适当位置；如果比
大时，则插入到
的"高端"的适当位置；
注释：
a) "低端"：因为 是辅助序列的第一个元素，即为顺序存储结构的第一个元素，因此，此处的"低端"是指
序列的高端部分的存储空间(即：
列表的右端部分的存储空间)；
b) "高端"：因为 是辅助序列的第一个元素，即为顺序存储结构的第一个元素，因此，此处的"高端"是指
序列的低端部分的存储空间(即：
列表的左端部分的存储空间)；
注意：
a) 关于此处如何定位到适当位置的问题，其实算法本身是没有明确要求，因此，我们可参考直接插入排序算法思想中的定位方法，也可以参考折半插入排序算法思想中的定位方法，甚至任何其他方法(只要认为高效的)均可。下文的具体编码参考实现中，使用的是直接插入排序算法思想中的定位方法，具体见编码参考。
03.重复步骤 02 直到全部处理完整个 序列为止；
04.将辅助空间 中的数据，拷贝到
序列列表中，排序完成；
注意：
a) 2路插入排序算法在实现时，一般情况下是需要设置两个游标指针 first 与 last。其中 first 指示 的低端下界位置；last 指示
的高端上界位置；
b) 在处理上面 04点时，要先按顺序拷贝低端部分的数据，然后再按顺序拷贝高端部分的数据；
算法的编码参考如下：
1 // 2 // summary : 2路插入排序 3 // in param : seqlist 待排序列表(数组).即是输入也是输出. 4 // in param : helplist 辅助列表(数组) 5 // in param : nLen 列表长度 6 // out param : -- 7 // return : -- 8 // !!!note : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效. 9 // 02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的. 10 void two_way_insert_sort(int seqlist[/*nLen*/], int helplist[/*nLen*/], const int nLen) { 11 helplist[0] = seqlist[0]; 12 auto first = 0; // 已排好序的低端(即:最小值的一端).所在位置即为最小值位置索引. 13 auto last = 0; // 已排好序的高端(即:最大值的一端).所在位置即为最大值位置索引. 14 auto nTemp = 0; 15 auto nInnerIdx = 0; 16 auto nPriorIdx = 0; 17 for (auto nOuterIdx = 1; nOuterIdx < nLen; ++nOuterIdx) { 18 nTemp = seqlist[nOuterIdx]; 19 if (nTemp < helplist[first]) { 20 first = (first - 1 + nLen) % nLen; 21 helplist[first] = nTemp; 22 } else if (nTemp >= helplist[last]) { 23 ++last; 24 helplist[last] = nTemp; 25 } else { 26 nInnerIdx = ++last; 27 while (nInnerIdx != first) { 28 nPriorIdx = (nInnerIdx - 1 + nLen) % nLen; 29 if (nTemp >= helplist[nPriorIdx]) { 30 break; 31 } 32 helplist[nInnerIdx] = helplist[nPriorIdx]; 33 nInnerIdx = nPriorIdx; 34 } 35 helplist[nInnerIdx] = nTemp; 36 } 37 } 38 auto nCounter = 0; 39 while (nCounter < nLen) { 40 seqlist[nCounter] = helplist[(first + nCounter) % nLen]; 41 ++nCounter; 42 } 43 }
原文：http://www.cnblogs.com/tongy0/p/5720889.html
