Author: bakari Date: 2012.7.21
排序算法有很多种，每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为插入排序。
插入排序有三种形式：
转载引用请注明出处：http://www.cnblogs.com/bakari/archive/2012/08/11/2633636.html 谢谢！
一、最简单的直接插入排序，每个元素之间选取的间隔为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 }
