经典四讲贯通C++排序之三 交换排序(1)

我们都知道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)时，可以看出，在完全有序的情况下，起泡比直插要好一些，因为此时不需要移动记录。