我們都知道C++排序方法中，有四種常用方法插入排序、希爾排序、交換排序以及選擇排序。在前面兩篇文章中，我們介紹了C++兩種排序方法——插入排序和希爾排序，這篇文章我們介紹C++排序的第三種方法——交換排序。本系列文章統一 測試程序）
交換排序
基本思想是：兩兩比較待排序記錄的關鍵碼，如果發生逆序，則交換之，直到所有對象都排好為止。
起泡排序
起泡排序是比較相鄰的兩個記錄，逆序則交換。這樣的做法導致小的關鍵碼一層層的浮上來，因此得名。51cto的論壇曾經討論過“冒泡”和“起泡”是不是一個東西，看來這是翻譯惹的禍，英文名都是Bubble Sort，具體寫的時候可以正著排，也可以倒著排。(嚴版是從後往前排，殷版是從前往後排，好在兩本書都翻譯為“起泡排序”，不然就正像某些人得出的結論——一個是從後往前排，一個是從前往後排)
- template <class T>
- void BubbleSort(T a[], int N, int& KCN, int& RMN)
- {
- KCN = 0; RMN = 0; bool exchange = true;
- for (int i = 1; i < N && exchange; i++)
- for (int j = N - 1; j >= i; j--)
- {
- exchange = false;
- if (++KCN && a[j - 1] > a[j]) { swap(a[j - 1], a[j]); exchange = true; RMN += 3; }
- }
- }
需要注意的是，不要寫成下面這個樣子，雖然結果是對的：
- template <class T>
- void BubbleSort2(T a[], int N)
- {
- for (int i = 0; i < N; i++)
- for (int j = 1; j < N - i; j++)
- if (a[j - 1] > a[j]) swap(a[j - 1], a[j]);
- }
測試結果：
- Sort ascending N=10000 TimeSpared: 0ms
- KCN=9999 KCN/N=0.9999 KCN/N^2=9.999e-005 KCN/NlogN=0.07525
- RMN=0 RMN/N=0 RMN/N^2=0 RMN/NlogN=0
- Sort randomness N=10000 TimeSpared: 1161ms
- KCN=45409094 KCN/N=4540.91 KCN/N^2=0.454091 KCN/NlogN=341.737
- RMN=71526984 RMN/N=7152.7 RMN/N^2=0.71527 RMN/NlogN=538.294
- Sort descending N=10000 TimeSpared: 1022ms
- KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
- RMN=149985000 RMN/N=14998.5 RMN/N^2=1.49985 RMN/NlogN=1128.75
可以看出，效率非常的差，還不如直插排序，真不知道為什麼人們對此津津樂道，難道是為了理解快速排序?另外還有一個有趣的現象，雖然逆序的KCN和RMN都比亂序的多，但是逆序花的時間卻比亂序少，從這裡可以看到CPU流水線的作用，這裡可以給我們一個信號，一個真正好的算法需要充分利用硬件的特性。增多記錄數目(N=1000000)時，可以看出，在完全有序的情況下，起泡比直插要好一些，因為此時不需要移動記錄。
