數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)(C++)之排序

2019-11-17 05:10:27

字體：大中小

供稿：網(wǎng)友

　　測試程序

　　后面的例程，都是對數(shù)組的排序，使用靜態(tài)鏈表的也適用于鏈表的排序。為簡單起見，只對單要害碼排序，并且最后的結(jié)果都是從頭到尾按升序排列。下面是統(tǒng)一的測試程序：

#include <iostream>
#include <iomanip>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "InsertSort.h"
#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))
#define N 10000 //排序元素的數(shù)目
#define SORT InsertSort //排序方法
class timer//單位ms
{
public:
void start() { start_t = clock(); }
clock_t time() { return (clock() - start_t); }
PRivate:
clock_t start_t;
};
int KCN, RMN; timer TIMER;
void test(int a[])
{
TIMER.start();
SORT<int>(a, N, KCN, RMN);
cout << "/tTimeSpared: " << TIMER.time() << "ms" << endl;
cout << "KCN=" << left << setw(11) << KCN;
cout << "KCN/N=" << left << setw(11)<< (double)KCN/N;
cout << "KCN/N^2=" << left << setw(11)<< (double)KCN/N/N;
cout << "KCN/NlogN=" << left << setw(11)<< (double)KCN/N/log((double)N)*log(2.0) << endl;
cout << "RMN=" << left << setw(11) << RMN;
cout << "RMN/N=" << left << setw(11)<< (double)RMN/N;
cout << "RMN/N^2=" << left << setw(11)<< (double)RMN/N/N;
cout << "RMN/NlogN=" << left << setw(11)<< (double)RMN/N/log((double)N)*log(2.0) << endl;
}
int main()
{
int i;
//randomize();為了在相同情況下比較各個排序算法，不加這句
int* ascending = new int[N];//升序序列
int* descending = new int[N];//降序序列
int* randomness = new int[N];//隨機(jī)序列
for (i = 0; i < N; i++) { ascending[i] = i; randomness[i] = i; descending[i] = N - i - 1;}
for (i = 0; i < N; i++) swap(randomness[i], randomness[random(N)]);
cout << "Sort ascending N=" << N; test(ascending);
cout << "Sort randomness N=" << N; test(randomness);
cout << "Sort descending N=" << N; test(descending);
return 0;
}
　　需要說明一點(diǎn)，KCN（要害碼比較次數(shù)）、RMN（記錄移動次數(shù)）并不是算法必須的，是為了對算法的性能有個直觀的評價（不用那些公式算來算去）。對10000個整數(shù)排序應(yīng)該是最省事的測試手段，建議不要再增多記錄數(shù)目了，一是在最壞的情況不用等太久的時間，二是避免KCN、RMN溢出，另外有些遞歸的算法在情況比較糟的時候，記錄數(shù)目太多堆棧可能會溢出，導(dǎo)致程序崩潰。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

插入排序

　　基本思想是，每步將一個待排序的記錄，按其要害碼大小，插入到前面已經(jīng)排好序的記錄的適當(dāng)位置，從頭做到尾就可以了。

　　直接插入排序

template <class T>
void InsertSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int i = 1; i < N; i++)
{
T temp = a[i]; RMN++;
for (int j = i; j > 0 && ++KCN && temp < a[j - 1]; j--) { a[j] = a[j - 1]; RMN++; }
a[j] = temp; RMN++;
}
}
　　精簡之后就是這樣：

template<class T> void InsertSort(T a[], int N)
{
for (int i = 1; i < N; i++)
{
T temp = a[i];
for (int j = i; j > 0 && temp < a[j - 1]; j--) a[j] = a[j - 1];
a[j] = temp;
}
}
　　測試結(jié)果：

Sort ascending N=10000 TimeSpared: 0ms
KCN=9999 KCN/N=0.9999 KCN/N^2=9.999e-005 KCN/NlogN=0.07525
RMN=19998 RMN/N=1.9998 RMN/N^2=0.00019998 RMN/NlogN=0.1505
Sort randomness N=10000 TimeSpared: 330ms
KCN=24293730 KCN/N=2429.37 KCN/N^2=0.242937 KCN/NlogN=182.829
RMN=24303739 RMN/N=2430.37 RMN/N^2=0.243037 RMN/NlogN=182.904
Sort descending N=10000 TimeSpared: 711ms
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
RMN=50014998 RMN/N=5001.5 RMN/N^2=0.50015 RMN/NlogN=376.4
　　可以看出，平均性能近似為n2/4，書上沒有騙人（廢話，多少人做過多少試驗(yàn)才得出的結(jié)論）。

　　折半插入排序

　　將直插排序中的搜索策略由順序搜索變?yōu)檎郯胨阉鳎隳艿玫酱朔N排序方法。顯而易見，只能減少KCN，不能減少RMN，所能帶來的性能提升也不會太大。

template<class T>
void BinaryInsertSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int i = 1; i < N; i++)
{
T temp = a[i]; RMN++; int low = 0, high = i - 1;
while (low <= high)//折半查找
{
int mid = (low + high) / 2;
if (++KCN && temp < a[mid]) high = mid - 1; else low = mid + 1;
}
for (int j = i - 1; j >= low; j--) { a[j + 1] = a[j]; RMN++; }//記錄后移
a[low] = temp; RMN++;//插入
}
}
　　測試結(jié)果：

Sort ascending N=10000 TimeSpared: 0ms
KCN=123617 KCN/N=12.3617 KCN/N^2=0.00123617 KCN/NlogN=0.930311
RMN=19998 RMN/N=1.9998 RMN/N^2=0.00019998 RMN/NlogN=0.1505
Sort randomness N=10000 TimeSpared: 320ms
KCN=118987 KCN/N=11.8987 KCN/N^2=0.00118987 KCN/NlogN=0.895466
RMN=24303739 RMN/N=2430.37 RMN/N^2=0.243037 RMN/NlogN=182.904
Sort descending N=10000 TimeSpared: 631ms
KCN=113631 KCN/N=11.3631 KCN/N^2=0.00113631 KCN/NlogN=0.855158
RMN=50014998 RMN/N=5001.5 RMN/N^2=0.50015 RMN/NlogN=376.4
　　可以看到KCN近似為nlog2n，有一定的性能提升。

　　表插入排序

　　假如用“指針”來表示記錄間的順序，就可以避免大量的記錄移動，當(dāng)然，最后還是要根據(jù)“指針”重排一下。自然的，折半查找在這里用不上了。

template <class T>
void TableInsertSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
int* link = new int[N]; int head = 0, pre, cur, i; link[0] = -1;
for (i = 1; i < N; i++)
{
if (a[head] > a[i]) { link[i] = head; head = i; KCN++;}//沒設(shè)表頭，因此需要此判定，失敗時此次判定沒記入KCN
else
{
for (cur = head; cur != -1&& ++KCN && a[cur] <= a[i]; cur = link[cur]) pre = cur;
link[pre] = i; link[i] = cur;
}
}
cur = head;//重排序列
for (i = 0; i < N; i++)
{
while (cur < i) cur = link[cur];
pre = link[cur];
if (cur != i)
{
swap(a[i], a[cur]); RMN += 3;
link[cur] = link[i]; link[i] = cur;
}
cur = pre;
}
delete []link;
}
　　測試結(jié)果：

Sort ascending N=10000 TimeSpared: 751ms
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: 621ms
KCN=25721250 KCN/N=2572.13 KCN/N^2=0.257213 KCN/NlogN=193.572
RMN=29955 RMN/N=2.9955 RMN/N^2=0.00029955 RMN/NlogN=0.225434
Sort descending N=10000 TimeSpared: 0ms
KCN=9999 KCN/N=0.9999 KCN/N^2=9.999e-005 KCN/NlogN=0.07525
RMN=15000 RMN/N=1.5 RMN/N^2=0.00015 RMN/NlogN=0.112886
　　可以看到，確實(shí)減少了RMN，理論上RMNmax＝3（n－1）。然而，就平均情況而言，性能還不如簡單的直插——這是由于測試對象是整數(shù)的緣故。對于鏈表來說，這種方法就不需要最后的重排了。關(guān)于重排的算法在嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》上有具體的說明。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

　　希爾排序

　　前面的算法的平均效率都不怎么好，但我們注重到直插排序在要害碼基本有序的情況下，效率是最好的，并且，在要害碼的數(shù)量很少的時候，n和n2的差距也不是那么的明顯。基于以上的事實(shí)，D.L.Shell在1959年（老古董了）提出了縮小增量排序，基本思想是：取一個間隔（gap），將序列分成若干的子序列，對每個子序列進(jìn)行直插排序；然后逐漸縮小間隔，重復(fù)以上過程，直到間隔為1。在開始的時候，每個子序列里要害碼很少，直插的效率很高；隨著間隔的縮小，子序列的要害碼越來越多，但是在前面的排序基礎(chǔ)上，要害碼已經(jīng)基本有序，直插的效率依然很高。

　　希爾排序的時間復(fù)雜度不好估量，gap的選取也沒有定論，gap＝[gap/2]的程序是最好寫的，至于為什么，寫寫就知道了。

template <class T>
void ShellSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int gap = N/2; gap; gap = gap/2)
for (int i = gap; i < N; i++)
{
T temp = a[i]; RMN++;
for (int j = i; j >= gap && ++KCN && temp < a[j - gap]; j -= gap)
{ a[j] = a[j - gap]; RMN++; }
a[j] = temp; RMN++;
}
}
　　測試結(jié)果：

Sort ascending N=10000 TimeSpared: 0ms
KCN=120005 KCN/N=12.0005 KCN/N^2=0.00120005 KCN/NlogN=0.903128
RMN=240010 RMN/N=24.001 RMN/N^2=0.0024001 RMN/NlogN=1.80626
Sort randomness N=10000 TimeSpared: 10ms
KCN=258935 KCN/N=25.8935 KCN/N^2=0.00258935 KCN/NlogN=1.94868
RMN=383849 RMN/N=38.3849 RMN/N^2=0.00383849 RMN/NlogN=2.88875
Sort descending N=10000 TimeSpared: 10ms
KCN=172578 KCN/N=17.2578 KCN/N^2=0.00172578 KCN/NlogN=1.29878
RMN=302570 RMN/N=30.257 RMN/N^2=0.0030257 RMN/NlogN=2.27707
　　注重到這時的測試結(jié)果很不準(zhǔn)確了，10000個整數(shù)的排序已經(jīng)測試不出什么來了（估計新機(jī)器都是0ms，我這里也有個別的時候全是0）。因此，下面用100000個整數(shù)的排序重新測試了一次：

Sort ascending N=100000 TimeSpared: 140ms
KCN=1500006 KCN/N=15.0001 KCN/N^2=0.000150001KCN/NlogN=0.903094
RMN=3000012 RMN/N=30.0001 RMN/N^2=0.000300001RMN/NlogN=1.80619
Sort randomness N=100000 TimeSpared: 230ms
KCN=4041917 KCN/N=40.4192 KCN/N^2=0.000404192KCN/NlogN=2.43348
RMN=5598883 RMN/N=55.9888 RMN/N^2=0.000559888RMN/NlogN=3.37086
Sort descending N=100000 TimeSpared: 151ms
KCN=2244585 KCN/N=22.4459 KCN/N^2=0.000224459KCN/NlogN=1.35137
RMN=3844572 RMN/N=38.4457 RMN/N^2=0.000384457RMN/NlogN=2.31466
　　這個結(jié)果表明，希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時間都不是很多，附加儲存是O(1)，的確非常不錯。在沒搞清楚快速排序、堆排序之前，它的確是個很好的選擇，我當(dāng)年一直用它。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

交換排序

　　基本思想是：兩兩比較待排序記錄的要害碼，假如發(fā)生逆序，則交換之，直到所有對象都排好為止。

　　起泡排序

　　起泡排序是比較相鄰的兩個記錄，逆序則交換。這樣的做法導(dǎo)致小的要害碼一層層的浮上來，因此得名。CSDN的論壇曾經(jīng)討論過“冒泡”和“起泡”是不是一個東西，看來這是翻譯惹的禍，英文名都是Bubble Sort，具體寫的時候可以正著排，也可以倒著排。（嚴(yán)版是從后往前排，殷版是從前往后排，好在兩本書都翻譯為“起泡排序”，不然就正像某些人得出的結(jié)論——一個是從后往前排，一個是從前往后排）

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; }
}
}
　　需要注重的是，不要寫成下面這個樣子，雖然結(jié)果是對的：

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]);
}
　　測試結(jié)果：

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
　　可以看出，效率非常的差，還不如直插排序，真不知道為什么人們對此津津樂道，難道是為了理解快速排序？另外還有一個有趣的現(xiàn)象，雖然逆序的KCN和RMN都比亂序的多，但是逆序花的時間卻比亂序少，從這里可以看到CPU流水線的作用，這里可以給我們一個信號，一個真正好的算法需要充分利用硬件的特性。增多記錄數(shù)目（N＝1000000）時，可以看出，在完全有序的情況下，起泡比直插要好一些，因?yàn)榇藭r不需要移動記錄。

　　快速排序

　　真為這個算法感到悲哀，連一個能表明算法實(shí)質(zhì)的名字（比如直插、表插）都沒有，也不像希爾排序是以發(fā)明人的名字命名的，難道就是因?yàn)樗炝耍恳苍S“快速”是對一個排序算法最高的榮譽(yù)吧。

　　基本思想是：任取待排序列的某個記錄作為基準(zhǔn)，按照該要害碼大小，將整個序列分成兩個序列——左側(cè)的所有記錄的要害碼都比基準(zhǔn)小（或者等），右側(cè)的都比基準(zhǔn)大，基準(zhǔn)則放在兩個子序列之間，顯然這時基準(zhǔn)放在了最后應(yīng)該放置的位置。分別對左右子序列重復(fù)上面的過程，直到最后所有的記錄都放在相應(yīng)的位置。

　　下面的例程不輕易看懂，因?yàn)檫@是幾次改進(jìn)之后的樣子：

template <class T>
int Partition(T a[], int left, int right, int& KCN, int& RMN)
{
int pivotpos = left; T pivot = a[left];//樞軸
for (int i = left + 1; i <= right; i++)
if (++KCN && a[i] < pivot && ++pivotpos != i)
{ swap(a[i], a[pivotpos]); RMN += 3;}
swap(a[left], a[pivotpos]); RMN += 3;
return pivotpos;
}
　　將計算樞軸位置單獨(dú)作為一個函數(shù)，可以避免遞歸的時候保存無用的臨時變量。當(dāng)你決定使用遞歸的時候，都要注重這點(diǎn)——將一切可以放在遞歸外面的都放在外面。注重這個函數(shù)是怎樣達(dá)到我們“樞軸左邊都比它小，右邊都比它大”的目的的。

template <class T>
void QSRecurve(T a[], int left, int right, int& KCN, int& RMN)
{
if (left < right)
{
int pivotpos = Partition<T>(a, left, right, KCN, RMN);
QSRecurve<T>(a, left, pivotpos - 1, KCN, RMN);
QSRecurve<T>(a, pivotpos + 1, right, KCN, RMN);
}
}
template <class T>
void QuickSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
QSRecurve<T>(a, 0, N - 1, KCN, RMN);
}
　　這兩個只能算個外殼了，尤其是最后一個。

　　測試結(jié)果：

Sort ascending N=10000 TimeSpared: 1051ms
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
RMN=29997 RMN/N=2.9997 RMN/N^2=0.00029997 RMN/NlogN=0.22575
Sort randomness N=10000 TimeSpared: 0ms
KCN=155655 KCN/N=15.5655 KCN/N^2=0.00155655 KCN/NlogN=1.17142
RMN=211851 RMN/N=21.1851 RMN/N^2=0.00211851 RMN/NlogN=1.59434
Sort descending N=10000 TimeSpared: 1082ms
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
RMN=29997 RMN/N=2.9997 RMN/N^2=0.00029997 RMN/NlogN=0.22575
　　可以看到，平均性能非常好，但是在兩端的性能還不如直插。測試N＝100000的情況如下（千萬記住把正序和逆序的測試注釋掉，否則，到時候“死機(jī)”不要找我）

Sort randomness N=100000 TimeSpared: 110ms
KCN=2123221 KCN/N=21.2322 KCN/N^2=0.000212322KCN/NlogN=1.27831
RMN=3010848 RMN/N=30.1085 RMN/N^2=0.000301085RMN/NlogN=1.81271
　　確實(shí)非常的“快速”，但是它的最壞情況實(shí)在讓人不能放心，萬一……，并且由于使用堆棧遞歸，出了最壞情況沒準(zhǔn)程序就崩潰了。為了減低這種不良傾向，改進(jìn)辦法是“三者取中”，即選取待排序序列的第一個、最后一個、中間一個的要害碼居中的那個作為基準(zhǔn)。只要改一下Partition函數(shù)就可以了。

template <class T>
int Partition(T a[], int left, int right, int& KCN, int& RMN)
{
int mid = (left + right) / 2;
if (++KCN && a[left] > a[mid])
{
if (++KCN && a[left] > a[right])
{
if (++KCN && a[mid] > a[right]) { swap(a[mid], a[left]); RMN += 3; }
else { swap(a[right], a[left]); RMN += 3; }
}
}
else
{
if (++KCN && a[left] < a[right])
{
if (++KCN && a[mid] < a[right]) { swap(a[mid], a[left]); RMN += 3; }
else { swap(a[right], a[left]); RMN += 3; }
}
}
int pivotpos = left; T pivot = a[left];//樞軸
for (int i = left + 1; i <= right; i++)
if (++KCN && a[i] < pivot && ++pivotpos != i) { swap(a[i], a[pivotpos]); RMN += 3;}
swap(a[left], a[pivotpos]); RMN += 3;
return pivotpos;
}
　　只是在原有的Partition函數(shù)上添加了粗體部分。下面是測試結(jié)果：

Sort ascending N=10000 TimeSpared: 0ms
KCN=131343 KCN/N=13.1343 KCN/N^2=0.00131343 KCN/NlogN=0.988455
RMN=35424 RMN/N=3.5424 RMN/N^2=0.00035424 RMN/NlogN=0.266592
Sort randomness N=10000 TimeSpared: 0ms
KCN=154680 KCN/N=15.468 KCN/N^2=0.0015468 KCN/NlogN=1.16408
RMN=204093 RMN/N=20.4093 RMN/N^2=0.00204093 RMN/NlogN=1.53595
Sort descending N=10000 TimeSpared: 280ms
KCN=12517506 KCN/N=1251.75 KCN/N^2=0.125175 KCN/NlogN=94.2036
RMN=45006 RMN/N=4.5006 RMN/N^2=0.00045006 RMN/NlogN=0.338704
　　下面是N＝100000的測試結(jié)果，在逆序的時候還是很尷尬，不過還算說得過去。

Sort ascending N=100000 TimeSpared: 60ms
KCN=1665551 KCN/N=16.6555 KCN/N^2=0.000166555KCN/NlogN=1.00276
RMN=393210 RMN/N=3.9321 RMN/N^2=3.9321e-005RMN/NlogN=0.236736
Sort randomness N=100000 TimeSpared: 110ms
KCN=1888590 KCN/N=18.8859 KCN/N^2=0.000188859KCN/NlogN=1.13704
RMN=2659857 RMN/N=26.5986 RMN/N^2=0.000265986RMN/NlogN=1.60139
Sort descending N=100000 TimeSpared: 42120ms
KCN=1250175006 KCN/N=12501.8 KCN/N^2=0.125018 KCN/NlogN=752.68
RMN=450006 RMN/N=4.50006 RMN/N^2=4.50006e-005RMN/NlogN=0.270931
　　然而實(shí)際上，我們花那么多語句搞一個“三者取中”還不如直接“隨便選一個”來得高效，例如將下面的語句替換掉原來的粗體語句：

swap(a[left], a[rnd(right-left)+left]); RMN += 3;
　　測試結(jié)果：

Sort ascending N=100000 TimeSpared: 90ms
KCN=1917756 KCN/N=19.1776 KCN/N^2=0.000191776KCN/NlogN=1.1546
RMN=378810 RMN/N=3.7881 RMN/N^2=3.7881e-005RMN/NlogN=0.228066
Sort randomness N=100000 TimeSpared: 120ms
KCN=1979189 KCN/N=19.7919 KCN/N^2=0.000197919KCN/NlogN=1.19159
RMN=3175977 RMN/N=31.7598 RMN/N^2=0.000317598RMN/NlogN=1.91213
Sort descending N=100000 TimeSpared: 110ms
KCN=2069369 KCN/N=20.6937 KCN/N^2=0.000206937KCN/NlogN=1.24588
RMN=2574174 RMN/N=25.7417 RMN/N^2=0.000257417RMN/NlogN=1.54981
　　可以看到逆序的效率有了質(zhì)的飛躍，隨機(jī)函數(shù)得自己寫，因?yàn)閹旌瘮?shù)的rand()最大只能輸出0x7fff，這是因?yàn)閞and函數(shù)使用的是32bit的整數(shù)，為了不溢出（最嚴(yán)重的是出負(fù)數(shù)），只能輸出那么大。一個不太嚴(yán)格的隨機(jī)函數(shù)如下，最大輸出值是32bit的最大正整數(shù)：

int rnd(int n)
{
static _int64 x;
x = (2053 * x + 13849) % 0x7fffffff;
return (int)x % n;
}

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

選擇排序

　　基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點(diǎn)是0，按此說法，第0小的記錄實(shí)際上就是最小的，有點(diǎn)別扭，不管這么多了）。當(dāng)i＝N－1時就排完了。

　　直接選擇排序

　　直選排序簡單的再現(xiàn)了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，假如不做某種非凡處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復(fù)雜度就是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; }
}
}
　　測試結(jié)果：

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)的亂序還多。一是說明測試精度不夠，在我的機(jī)器上多次測試結(jié)果上下浮動10ms是常有的事；二是說明和KCN的n(n-1)/2相比，RMN的3(n-1)有些微不足道。

　　錦標(biāo)排序

　　從直選排序看來，算法的瓶頸在于KCN，而實(shí)際上，對于后續(xù)的尋找最小值來說，時間復(fù)雜度可以降到O(logn)。最為直接的做法是采用錦標(biāo)賽的辦法，將冠軍拿走之后，只要把冠軍打過的比賽重賽一遍，那么剩下的人中的“冠軍”就產(chǎn)生了，而重賽的次數(shù)就是競賽樹的深度。實(shí)際寫的時候，弄不好就會寫得很“蠢”，不只多余占用了大量內(nèi)存，還會導(dǎo)致無用的判定。我沒見過讓人滿足的例程（殷版上的實(shí)在太惡心了），自己又寫不出來漂亮的，也就不獻(xiàn)丑了（其實(shí)這是惰性的緣故，有了快排之后，大多數(shù)人都不會對其他內(nèi)排感愛好，除了基數(shù)排序）。實(shí)在無聊的時候，不妨寫（或者改進(jìn)）錦標(biāo)排序來打發(fā)時間，^_^。

　　堆排序

　　錦標(biāo)排序的附加儲存太多了，而高效的尋找最大值或最小值（O(logn)），我們還有一種方法是堆。這里使用了最大堆，用待排記錄的空間充當(dāng)堆空間，將堆頂?shù)挠涗洠壳白畲螅┖投训淖詈笠粋€記錄交換，當(dāng)堆逐漸縮小成1的時候，記錄就排序完成了。顯而易見的，時間復(fù)雜度為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;//不需調(diào)整，結(jié)束調(diào)整
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<T>(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);
}
}
　　測試結(jié)果，直接測試的是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，還沒有很糟的情況，假如實(shí)在不放心快排的最壞情況，堆排確實(shí)是個好選擇。這里仍然出現(xiàn)了KCN、RMN多的反而消耗時間少的例子——誤差70ms是不可能的，看來CPU優(yōu)化的作用還是非常明顯的（可能還和Cache有關(guān)）。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

上一篇：編程者說之C語言

下一篇：Visual C++ 入門精解－引言