排序——选择排序和插入排序

 1 /* 选择排序，参数为无序序列对应的数组和数组的长度，第三个参数是默认从小到大排列，此时可以不加这个参数；不稳定排序 */
 2     template <typename T>  // 两个 for 循环 ==> O(n*n)
 3     static void Select(T array[], int len, bool min2max = true)
 4     {     
 5         for(int i=0; i<len; i++)  // len 个数据分别和后面的作比较，这里是先写第 0 个的数据，然后看着要写很多所以又开始循环的
 6         {
 7             int min = i;  // 记录最小元素在数组里面的下标
 8 
 9             /* 在 i 后面（包括 i）的序列里找最小值，找到了当前的最小元素 */
10             for(int j=i+1; j<len; j++)  // 假设 i 是最小值，则和 i + 1 后面的元素比较；
11             {
12                 if( min2max ? (array[min] > array[j]) : ( array[min] < array[j] ) ) // 这里实现了两种方向的排序，当你考虑if 的时候，能不能考虑下三目运算符
13                 {         
14                     min = j;  // 这里将较小的下标给了 min，交换下标很经典，不要交换元素，否则排序属性就变了；
15                 }
16             }
17 
18             if( min != i ) // 当后面的最小值和最小值相等时候避免交换， CPU 可以//很快的完成比较，但是交换要调用函数，如果 T 是一个很复杂的类，则交换用的时间是非常多的，所以排序的时候尽量避开交换操作用比较操作
19         {
20                 Swap(array[i], array[min]);  // 找到整个无序序列的最小元素，并且把它放到了第 0 号位置；因为交换，所以选择排序是不稳定的排序法；交换是不稳定排序的根本原因
21         }
22         }
23 　　 }

 1 /* 插入排序 */
 2     template <typename T>
 3     static void Insert(T array[], int len, bool min2max = true)  // 插入排序是稳定排序，两个 for 循环 ==> O(n*n)
 4     {
 5         for(int i=1; i<len; i++)  // 第 0 号位的元素本身就可以实现插入，因为其本身就是有序的序列，所以没必要再从 0 号位插入
 6         {
 7             int k = i;
 8             T e = array[i];  // 将要插入的数据元素拿出来
 9 
10             for(int j=i-1; (j>=0)&&(min2max ? (array[j]>e) : (array[j]<e)); j--)  // 三目运算符决定排序方向
11             {
12                 array[j+1] = array[j];
13                 k = j;
14             }
15 
16             if( k != i )  // 当要比较的元素 array[i] 比前面要被插入的元素都大的时候， k = i, 这时不用赋值，太耗时
17             {
18                 array[k] = e;  // k 记录了比较后挪动的空位置下标；稳定排序，因为没有交换位置，只是顺序移动位置；
19             }
20         }
21 　　 }