經典四講貫通C++排序之四 選擇排序
我們都知道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)有些微不足道。
#p#
錦標排序
從直選排序看來，算法的瓶頸在于KCN，而實際上，對于后續的尋找最小值來說，時間復雜度可以降到O(logn)。最為直接的做法是采用錦標賽的辦法，將冠軍拿走之后，只要把冠軍打過的比賽重賽一遍，那么剩下的人中的“冠軍”就產生了，而重賽的次數就是競賽樹的深度。實際寫的時候，弄不好就會寫得很“蠢”，不只多余占用了大量內存，還會導致無用的判斷。我沒見過讓人滿意的例程(殷版上的實在太惡心了)，自己又寫不出來漂亮的，也就不獻丑了(其實這是惰性的緣故，有了快排之后，大多數人都不會對其他內排感興趣，除了基數排序)。實在無聊的時候，不妨寫(或者改進)錦標排序來打發時間，^_^。
堆排序
錦標排序的附加儲存太多了，而高效的尋找***值或最小值(O(logn))，我們還有一種方法是堆。這里使用了***堆，用待排記錄的空間充當堆空間，將堆頂的記錄(目前***)和堆的***一個記錄交換，當堆逐漸縮小成1的時候，記錄就排序完成了。顯而易見的，時間復雜度為O(nlogn)，并且沒有很糟的情況。
- template <class T>
- void FilterDown(T a[], int i, int N, int& KCN, int& RMN)
- {
- int child = 2 * i + 1; T temp = a[i];
- while (child < N)
- {
- if (child < N - 1 && a[child] < a[child+1]) child++;
- if (++KCN && temp >= a[child]) break;//不需調整，結束調整
- a[i] = a[child]; RMN++;
- i = child; child = 2 * i + 1;
- }
- a[i] = temp; RMN++;
- }
- template <class T>
- void HeapSort(T a[], int N, int& KCN, int& RMN)
- {
- int i;
- for (i = (N - 2)/2; i >= 0; i--) FilterDown
(a, i, N, KCN, RMN); //生成***堆- for (i = N - 1; i > 0; i--)
- {
- swap(a[0], a[i]); RMN += 3;
- FilterDown(a, 0, i, KCN, RMN);
- }
- }
測試結果，直接測試的是N=100000：
- Sort ascending N=100000 TimeSpared: 110ms
- KCN=1556441 KCN/N=15.5644 KCN/N^2=0.000155644KCN/NlogN=0.937071
- RMN=2000851 RMN/N=20.0085 RMN/N^2=0.000200085RMN/NlogN=1.20463
- Sort randomness N=100000 TimeSpared: 160ms
- KCN=3047006 KCN/N=30.4701 KCN/N^2=0.000304701KCN/NlogN=1.83448
- RMN=3898565 RMN/N=38.9857 RMN/N^2=0.000389857RMN/NlogN=2.34717
- Sort descending N=100000 TimeSpared: 90ms
- KCN=4510383 KCN/N=45.1038 KCN/N^2=0.000451038KCN/NlogN=2.71552
- RMN=5745996 RMN/N=57.46 RMN/N^2=0.0005746 RMN/NlogN=3.45943
整體性能非常不錯，附加儲存1，還沒有很糟的情況，如果實在不放心快排的最壞情況，堆排確實是個好選擇。這里仍然出現了KCN、RMN多的反而消耗時間少的例子——誤差70ms是不可能的，看來CPU優化的作用還是非常明顯的(可能還和Cache有關)。
【編輯推薦】
