经典四讲贯通C++排序之四 选择排序(1)

我们都知道C++排序方法中，有四种常用方法插入排序、希尔排序、交换排序以及选择排序。这篇文章我们介绍选择排序。（本系列文章统一 测试程序）

选择排序

基本思想是：每次选出第i小的记录，放在第i个位置(i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了)。当i=N-1时就排完了。

直接选择排序

直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

template <class T>  
void SelectSort(T a[], int N, int& KCN, int& RMN)  
{  
KCN = 0; RMN = 0;  
for (int i = 0; i < N; i++)  
{  
for (int j = i + 1, k = i; j < N; j++) if (++KCN && a[j] < a[k]) k = j;//select min  
if (k != i) { swap(a[k], a[i]); RMN += 3; }  
}  
} 

测试结果：

Sort ascending N=10000 TimeSpared: 721ms  
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
RMN=0 RMN/N=0 RMN/N^2=0 RMN/NlogN=0  
Sort randomness N=10000 TimeSpared: 711ms  
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
RMN=29955 RMN/N=2.9955 RMN/N^2=0.00029955 RMN/NlogN=0.225434  
Sort descending N=10000 TimeSpared: 711ms  
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
RMN=15000 RMN/N=1.5 RMN/N^2=0.00015 RMN/NlogN=0.112886 

可以看到KCN固定为n(n-1)/2。另外一件有趣的事是，RMN=0的正序花的时间居然比RMN接近3(n-1)的乱序还多。一是说明测试精度不够，在我的机器上多次测试结果上下浮动10ms是常有的事;二是说明和KCN的n(n-1)/2相比，RMN的3(n-1)有些微不足道。