我們都知道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)有些微不足道。
