[编程珠玑读书笔记] 插入排序

这么简单的插入排序，都可以优化，还有什么是不可以优化的。最让我惊讶的是，当多次调用一个函数的时候，函数的调用开销是不可忽略的。正如测试结果所示：

#include<stdio.h>
#define MAX 1000000
void swap( int *data, int i, int j)
{
	int temp = data[i]; 
	data[i] = data[j];
	data[j] = temp;
}
//未经过优化的插入排序，简单直观
void InsertSort1( int *data, int n)
{
	int i, j;
	for( i = 1; i< n; i++)
		for( j = i; data[j - 1] > data[j] && j > 0; j--)
			swap(data, j-1, j);
}
//第一级优化的插入排序，将swap调用移到函数内部
void InsertSort2( int *data, int n)
{
	int i, j;
	int temp;
	for( i = 1; i< n; i++)
		for( j = i; data[j - 1] > data[j] && j > 0; j--)
		{
			temp = data[j - 1];
			data[j-1] = data[j];
			data[j] = temp;
		}

}
//第二级优化的插入排序，注意到每次交换data[j - 1] , data[j],中间有多余的操作
void InsertSort3( int *data, int n)
{
	int i, j, temp;
	for( i = 1; i< n; i++)
	{
		temp = data[i];
		for( j = i; data[j - 1] > data[j] && j > 0; j--)
			data[j ] = data[j - 1];
		data[j] = temp;	
	}
}
int main()
{
	//设置种子，每次产生的随机数一样
	srand(5);
	//用以测试程序运行时间
	double BegTime, EndTime;
	int i = 0;
	//待排序的数组
	int data[MAX];
	const int denominator = MAX * 10;	
	//初始化待排序数组
	for( i = 0; i < MAX; i++)
		data[i] = rand() % denominator;

	BegTime = clock();	
	InsertSort1( data, MAX); 
	EndTime = clock();	
	printf("time of InsertSort1 test is : %gms\n", (EndTime - BegTime) / 1000);

	//初始化待排序数组
	for( i = 0; i < MAX; i++)
		data[i] = rand() % denominator;

	BegTime = clock();	
	InsertSort2( data, MAX); 
	EndTime = clock();	
	printf("time of InsertSort2 test is : %gms\n", (EndTime - BegTime) / 1000);

	//初始化待排序数组
	for( i = 0; i < MAX; i++)
		data[i] = rand() % denominator;

	BegTime = clock();	
	InsertSort3( data, MAX); 
	EndTime = clock();	
	printf("time of InsertSort3 test is : %gms\n", (EndTime - BegTime) / 1000);
	return 0;
}

结果：

time of InsertSort1 test is : 20470ms
time of InsertSort2 test is : 13720ms
time of InsertSort3 test is : 8300ms