基本思想是：每次选出第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)有些微不足道。