闲着没事，做个小小的测试，测试一下冒泡，选择，插入和快速四种排序对同一个含有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;
}
测试结果如下图：
从上图可以看出，快排确实很快，冒泡让人无语，插入比选择稍快一些。