DoogooFeng Learn to C++

闲着没事，做个小小的测试，测试一下冒泡，选择，插入和快速四种排序对同一个含有1000000个元素的数组排序所用的时间，做个比较。

四种排序的代码如下：

冒泡排序：

template <typename T>
void bubble_sort(T a[], int num){
	if(num ==0 || num == 1)
		return ;
	bool changed = false;
	do{
		for(int i=0; i<num-1; i++){
			if(a[i] < a[i+1]){
				swap(a[i], a[i+1]);
				changed = true;
			}
		}
		
	}while(changed);
}

选择排序：

template <typename T>
void select_sort(T a[], int num){
	T min;
	int locate;//最小值位置
	for(int i=0; i<num-1; i++){
		min = a[i];
		//找最小值
		for(int j=i+1; j<num; j++){
			if(a[j] < min){
				locate = j;
			}
		}
		swap(a[i], a[locate]);
	}
}

插入排序：

template <typename T>
void insert_sort(T a[], int num){
	int j;
	int temp;//暂存无序区待插入元素
	for(int i=1; i<num; ++i){
		j = i;
		temp = a[i];
		//待插入元素与有序区元素一一比较
		while(j > 0 && temp < a[j-1]/*如果小于有序区被比较元素*/){
			//则将有序区元素后移
			a[j] = a[j-1];
			//将被比较元素前移一位
			--j;
		}
		//将待插入元素插入相应位置
		a[j] = temp;
	}
}

快速排序：

template <typename T>
void quick_sort(T a[], int num)
{
	//如果一个元素，不用排
	if(num ==1)
		return ;
	//如果只有两个元素没必要分界
	if(num == 2){
		if(a[1] < a[0])
			swap(a[1], a[0]);
		return ;
	}
	//取中间元素为界，希望可以将两部分尽量分的均匀一些
	swap(a[num/2], a[0]);
	T bound = a[0];
	//声明左右两个指针变量
	T* L = a+1;
	T* R = a+num-1;
	//作比较，不合适的交换，直至一趟排序完成
	while(L < R){
		while(L < R && *L < bound)
			++L;
		while(R >= L && *R > bound)
			--R;
		if(L < R)
			swap(*L, *R);
	}
	if(*R < bound)
		swap(*R, *a);
	//递归排序两个分开的子序列
	quick_sort(a, R-a);
	quick_sort(R+1, num-1-(R-a));
}

测试程序如下：

#include <iostream>
using namespace std;
#include <ctime>

int main()
{
	const int N=100000;
	int a[N];
	while(1){	
		for(int i=0; i<N; i++)
			a[i] = N-i;
		int choice;
		cout<<"1.bubble 2.insert 3.select 4.quick"<<endl;
		clock_t t1;
		clock_t t2;
		cin >> choice;
		switch(choice)
		{
			case 1:
				t1 = clock();
				bubble_sort(a, N);
				t2 = clock();
				break;
			case 2:
				t1 = clock();
				insert_sort(a, N);
				t2 = clock();
				break;
			case 3:
				t1 = clock();
				select_sort(a, N);
				t2 = clock();
				break;
			case 4:
				t1 = clock();
				quick_sort(a, N);
				t2 = clock();
				break;
		}
		cout << double(t2-t1)/CLOCKS_PER_SEC << endl;
	}	
	return 0;
}

测试结果如下图：

从上图可以看出，快排确实很快，冒泡让人无语，插入比选择稍快一些。