经典四讲贯通C++排序之一 插入排序(1)

我们都知道C++排序方法中，有四种常用方法插入排序、希尔排序、交换排序以及选择排序。这篇文章我们介绍插入排序。在介绍插入之前，先引入我们整个系列文章中的测试程序。

测试程序

后面的例程，都是对数组的排序，使用静态链表的也适用于链表的排序。为简单起见，只对单关键码排序，并且最后的结果都是从头到尾按升序排列。下面是统一的测试程序：

#include   
#include   
using namespace std;  
#include   
#include   
#include   
#include "InsertSort.h"  
#define random(num) (rand() % (num))  
#define randomize() srand((unsigned)time(NULL))  
#define N 10000 //排序元素的数目  
#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];//随机序列  
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;  
} 

需要说明一点，KCN(关键码比较次数)、RMN(记录移动次数)并不是算法必须的，是为了对算法的性能有个直观的评价(不用那些公式算来算去)。对10000个整数排序应该是最省事的测试手段，建议不要再增多记录数目了，一是在最坏的情况不用等太久的时间，二是避免KCN、RMN溢出，另外有些递归的算法在情况比较糟的时候，记录数目太多堆栈可能会溢出，导致程序崩溃。