排序——冒泡排序和希尔排序

 1 /* 冒泡排序 */
 2     template <typename T>
 3     static void Bubble(T array[], int len, bool min2max = true)  // O(n*n) 最坏情况下，冒泡排序的较其他排序要多一点点
 4     {
 5         bool exchange = true;  // 标记位，是否发生了交换，不交换时候就排好序了；不一定是最坏排序，取决于这个 exchange
 6         for(int i=0; (i<len) && exchange; i++)  // 标记位为假，则没有交换，那么就排序好了；最坏情况下这个循环要做完
 7         {
 8             exchange= false;  // 还没有排序，还没有交换
 9 
10             /* 具体的冒泡操作，从后向前，前面 i 个位置已经排好序了，所以 j>i；最//坏情况下这个循环要做完 */
11             for(int j=len-1; j>i; j--)
12             {
13                 if( min2max ? (array[j]<array[j-1]) : (array[j]>array[j-1]) )   // 发生逆序
14                 {
15                     Swap(array[j], array[j-1]);  // 交换
16                     exchange = true;  // 交换了
17                 }
18             }
19         }
20 }

 1 /* 希尔排序 */
 2     template <typename T>
 3     static void Shell(T array[], int len, bool min2max = true) // 不稳定的排序法，O(n的1.5）
 4     {
 5         int d = len;  // 设置间隔为 len
 6 
 7         do  // 都做几次插入排序就可以得到更快的算法了
 8         {
 9             /* 数学角度证明这样比较好比较困难，但是实践证明这样比较好，这个公式保证了 d 大于 1，同时当 d 很大的时候，减小比较快，当 d 接近 1 的时候减小比较慢；而 d-- 不能提高效率*/
10             d = d / 3 + 1;
11 
12             for(int i=d; i<len; i+=d)  // 这里是插入排序，初始值和循环增量都是 d，代码从插入排序中更改过来
13             {
14                 int k = i;
15                 T e = array[i];  // 将要插入的数据元素拿出来
16                 for(int j=i-d; (j>=0)&&(min2max ? (array[j]>e) : (array[j]<e)); j-=d)  // 三目运算符决定排序方向
17                 {
18                     array[j+d] = array[j];
19                     k = j;
20                 }
21 
22                 if( k != i )  // 当要比较的元素 array[i] 比前面要被插入的元素都大的时候， k = i, 这事不用赋值，太耗时
23                 {
24                     array[k] = e;  // k 记录了比较后挪动的空位置下标
25                 }
26             }
27 
28         }while( d > 1 );
29 　　 }