闲来无事，拿出数据结构的排序算法做一比较：
第一种算法为选择排序，二为插入排序，三是冒泡排序，六是二分法插入排序，随机产生了10000个数字
#include "stdafx.h"
#include <iostream>
#include "windows.h"
#include "stdlib.h"
#include "time.h"
using namespace std;
const int count = 10000;
const int SELECT = 1;
const int INSERT = 2;
const int BUBBLE = 3;
const int HEAP = 4;
const int QUICK = 5;
const int BIINSERT =6;
void QuickSort(int a[],int start,int end)
{
int i,j;
if(start<end)
{
i = start;
j = end;
long lTemp = a[start];
do
{
while(i<j&&lTemp<a[j]) j--; //从最右开始找位置
if(i<j) //与左边交换后掉头
{
swap(a[j],a[i]);
i++;
}
while(i<j&&a[i]<lTemp) i++; 从左边找
if(i<j)
{
swap(a[j],a[i]);
j--;
}
} while(i<j); //最终找到定位的地方
a[i] = lTemp; //元素放入，分成两个序列
QuickSort(a,start,i-1); //左边序列
QuickSort(a,i+1,end); //右边序列
}
}
void swap(int &a,long &b)
{
long lTemp;
lTemp = a;
a = b;
b = lTemp;
}
void sort(int a[],int count,int lMethod)
{
switch(lMethod)
{
case SELECT:
{
//Selected Sort
for(int i=0;i<count;i++)
{
for(int j = i+1;j<count;j++)
{
if(a[j]>a[i])
{
swap(a[j],a[i]);
}
}
}
}
break;
case INSERT: //Insert Sort
{
long lTemp;
for(int i = 0;i<count;i++)
{
int j = i+1;
long lTemp = a[j] ; //
while(j>0&&lTemp<a[j-1])
{
a[j] = a[j-1];
j--;
}
a[j] = lTemp;
}
}
break;
case BUBBLE: //Bubble Sort
{
for(int i = 0;i< count;i++)
{
for(int j=i+1;j<count;j++)
{
if(a[j]<a[j-1])
{
long lTemp;
lTemp = a[j];
a[j]= a[j-1];
a[j-1] = lTemp;
}
}
}
}
break;
case HEAP: //Heap Sort
{
}
break;
case QUICK: //Quick Sort
{
QuickSort(a,0,count-1);
}
break;
case BIINSERT:
{
long lTemp;
for(int i = 0;i<count;i++)
{
int j = i+1;
long lTemp = a[j] ;
int k,m,n;
m = 0;n = j;
k = (m+n)/2;
while(m<n)
{
if(lTemp>a[k])
m = k+1;
else
n = k-1;
k = (m+n)/2;
}
for(int L=j ; L>k ; L--)
{
a[L] = a[L-1];
}
a[L] = lTemp;
}
}
break;
}
}
int main(int argc, char* argv[])
{
int a[count];
int b[count];
srand( (unsigned)time( NULL ) );
long lNum = 0;
for( int i = 0; i < count;i++ )
{
lNum = rand()%count;
if(i%10==0)
printf("\n");
printf( " %6d", lNum );
a[i] = lNum;
b[i] = lNum;
}
printf("\n");
long lStart = GetTickCount();
sort(a,count,1);
long lEnd = GetTickCount();
cout<<"SELECT sort times= "<<( lEnd - lStart)<<" uMinutes \n";
for( i = 0; i < count;i++ )
{
a[i] = b[i];
}
lStart = GetTickCount();
sort(a,count,2);
lEnd = GetTickCount();
cout<<"INSERTsort times= "<<( lEnd - lStart)<<" uMinutes \n";
for( i = 0; i < count;i++ )
{
a[i] = b[i];
}
lStart = GetTickCount();
sort(a,count,3);
lEnd = GetTickCount();
cout<<"BUBBLE sort times= "<<( lEnd - lStart)<<" uMinutes \n";
for( i = 0; i < count;i++ )
{
a[i] = b[i];
}
lStart = GetTickCount();
sort(a,count,6);
lEnd = GetTickCount();
cout<<"BIINSERT sort times= "<<( lEnd - lStart)<<" uMinutes \n";
for( i = 0; i < count;i++ )
{
a[i] = b[i];
}
lStart = GetTickCount();
sort(a,count,5);
lEnd = GetTickCount();
cout<<"QUICK sort times= "<<( lEnd - lStart)<<" uMinutes \n";
for( int j = 0; j < count;j++ )
{
// if(j%10==0)
// printf("\n");
// printf( " %6d", a[j] );
}
return 0;
}
下面是测试结果：
一次：
SELECT sort times= 1078 uMinutes
INSERTsort times= 156 uMinutes
BUBBLE sort times= 438 uMinutes
BIINSERT sort times= 141 uMinutes
QUICK sort times= 0 uMinutes
二次：
SELECT sort times= 1047 uMinutes
INSERTsort times= 156 uMinutes
BUBBLE sort times= 453 uMinutes
BIINSERT sort times= 141 uMinutes
QUICK sort times= 0 uMinutes
三次：
SELECT sort times= 1063 uMinutes
INSERTsort times= 156 uMinutes
BUBBLE sort times= 437 uMinutes
BIINSERT sort times= 141 uMinutes
QUICK sort times= 15 uMinutes
从测试结果中可以看到，数据量大的时候，二分法插入排序的性能较好。快速排序最佳
冒泡排序由于是稳定的排序方法，排序性能适中，比较适合使用，当数据量大、不要求稳定排序时可以考虑二分法或快速，堆排序。
小数据量时用插入或冒泡排序就够了，针对随机数，通常不要使用选择排序。