经典排序之 插入排序

 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 }

 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 }