开了个公众号「aCloudDeveloper」，专注技术干货分享，期待与你相遇。
Author: bakari Date: 2012.7.21
排序算法有很多种，每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为插入排序。
插入排序有三种形式：
转载引用请注明出处： 谢谢！
一、最简单的直接插入排序，每个元素之间选取的间隔为1
见代码：
1 /***************************************************** 2 * Author: bakari Date: 2012.7.21 3 * 直接插入排序 4 * 存储结构--vector 5 *****************************************************/ 6 void InsertSort::Insort() 7 { 8 for(int i = 1; i != len; ++i) 9 {10 int InsertPoint = insertList[i];11 int iReplace = i;12 while(iReplace > 0 && InsertPoint < insertList[iReplace - 1])13 {14 insertList[iReplace] = insertList[iReplace - 1]; //移动填补15 iReplace --;16 }17 insertList[iReplace] = InsertPoint; //插入18 }19 }
二 、shell排序：
shell排序其实本质是插入排序，只不过是分区间，然后在不同的区间去进行排序。
看代码：
1 /*********************************************** 2 * shell排序 3 * 在直接插入排序的基础上增加间隔 4 * 算法和直接插入一致 5 ***********************************************/ 6 void ShellSort::Shell_Sort() 7 { 8 int gap = len / 2; //确定间隔，初始间隔为序列长度的一半，而后继续缩小进行 9 while(gap)10 {11 for (int i = gap;i < len; i += gap)12 {13 int ShellPoint = ShellList[i];14 int j = i;15 while(j > 0 && ShellPoint < ShellList[j - gap])16 {17 ShellList[j] = ShellList[j - gap];18 j -= gap;19 }20 ShellList[j] = ShellPoint;21 }22 gap /= 2; //继续缩小间隔，直到间隔为1；23 }24 }
三、二叉插入排序
这个和二叉查找类似，找不到元素之后就进行插入，直到排序完为止。
看代码：
1 /**************************************************** 2 * 二叉插入排序 3 * 原理与二叉查找相似，找不到元素则进行插入 4 ****************************************************/ 5 6 //插入排序实现 7 void BinaryInsertSort::Binary_Insert_Sort() 8 { 9 int mid; //记录中点位置10 for (int i = 0; i != len; ++i)11 {12 int BInsertPoint = BInsertList[i];13 int left = 0;14 int right = i - 1;15 while(left <= right)16 {17 mid = (left + right) / 2;18 if(BInsertPoint < BInsertList[mid])19 right = mid - 1;20 else left = mid + 1;21 }22 for(int j = i; j > left ;j--)23 BInsertList[j] = BInsertList[j - 1];24 BInsertList[left] = BInsertPoint;25 }26 }