[原创]各种排序方法总结【2008年7月7日更新】
代码全部重新编写，去掉了一些很dirty的地方，并增加了几种排序方法。现在一共收录了插入，选择，冒泡，归并，希尔，堆排，快排，计数等八种常用的排序方法，并做了效率比较，其中对1万个随机数排序使用了所有的方法，而对100万个随机数排序则只使用了后五种高级排序，因为对于简单排序，速度已经慢得难以忍受了……有耐心的朋友倒是可以等等，看看究竟需要多少时间。
[bo]五月14日更新了归并排序，按照飞燕的提示只分配了一个数组，速度快了近一倍！虽然还是没有超过希尔排序:)[/bo]
每个排序都经过简单的测试，如果发现有实现错误导致产生错误的结果，请跟帖反映，不胜感激~~~~
在我的电脑上运行如下（Athron64x2 3600+，2G内存，Vista操作系统，GCC编译器）:
程序代码：一万个数字对所有排序的测试： InsertSort Use time:31ms SelectSort Use time:100ms BubbletSort Use time:222ms CountSort Use time:0ms QuickSort Use time:1ms HeapSort Use time:1ms ShellSort Use time:2ms MergeSort Use time:5ms 100万个数字，对高级排序的测试： CountSort Use time:9ms QuickSort Use time:135ms HeapSort Use time:354ms ShellSort Use time:570ms MergeSort Use time:609ms 请按任意键继续. . .下面是源代码：
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include <ctime>
#include <iostream>
using namespace std;
#define SWAP(i,j) {int t=(i);(i)=(j);(j)=t;}
//插入排序
void InsertSort(int*a,int len)
{
for (int i=1;i<len;i++)
{
int j=i,x=a[i];
while (j && a[j-1]>x)a[j]=a[j-1],j--;
a[j]=x;
}
}
//选择排序
void SelectSort(int*a,int len)
{
for (int i=1,j,k;i<len;i++)
{
for (j=i,k=i-1;j<len;j++)
if (a[j]<a[k])k=j;
if (k>=i)SWAP(a[i-1],a[k]);
}
}
//冒泡排序
void BubbletSort(int*a,int len)
{
for (bool bSwap=true;bSwap;len--)
{
bSwap=false;
for (int j=1;j<len;j++)
if (a[j-1]>a[j]){SWAP(a[j-1],a[j]);bSwap=true;}
}
}
//计数排序
void CountSort(int*a,int len)
{
int c[RAND_MAX+1]={0};
for (int i=0;i<len;i++)c[a[i]]++;
for (int i=RAND_MAX;i>=0;)
if (c[i])a[--len]=i,c[i]--; else i--;
}
//堆调整
void HeapAdjust(int *a,int root,int len)
{
int child,x=a[root];
while (child=root<<1|1,child<len)
{
if (child<len-1 && a[child]<a[child+1])child++;
if (x<a[child]){a[root]=a[child];root=child;}
else break;
}
a[root]=x;
}
//堆排序
void HeapSort(int*a,int len)
{
for (int i=len/2-1;i>=0;i--)
HeapAdjust(a,i,len);
while (--len)
{
SWAP(a[0],a[len]);
HeapAdjust(a,0,len);
}
}
//归并
void Merge(int*a,int center,int len)
{
int *tmp=new int[len+2];
for (int i=0;i<center;i++)tmp[i]=a[i];
for (int i=center+1;i<=len;i++)tmp[i]=a[i-1];
tmp[center]=tmp[len+1]=INT_MAX;
for (int i=0,j=center+1,k=0;k<len;k++)
a[k]=tmp[(tmp[i]<tmp[j]?i:j)++];
delete[] tmp;
}
//归并排序
void MergeSort(int*a,int len)
{
if (len>1)
{
int c=len/2;
MergeSort(a,c);
MergeSort(a+c,len-c);
Merge(a,c,len-c);
}
}
//划分
int Partition(int*a,int len)
{
int x=a[--len],i=-1;
for (int j=0;j<len;j++)
if (a[j]<x){i++;SWAP(a[i],a[j]);}
SWAP(a[i+1],a[len]);
return i+1;
}
//快速排序
void QuickSort(int*a,int len)
{
if (len > 0)
{
int q=Partition(a,len);
if (q<len-q)
{
QuickSort(a,q);
QuickSort(a+q+1,len-q-1);
}
else
{
QuickSort(a+q+1,len-q-1);
QuickSort(a,q);
}
}
}
//希尔插入
void ShellInsert(int*a,int inc,int len)
{
for (int i=inc;i<len;i+=inc)
{
int j=i,x=a[i];
while (j>0 && a[j-inc]>x)a[j]=a[j-inc],j-=inc;
a[j]=x;
}
}
//插入式希尔排序
void ShellSort(int*a,int len)
{
int inc=len;
do
{
inc=inc/3+1;
for (int s=0;s<inc;s++)
ShellInsert(a-s,inc,len+s);
}
while (inc>1);
}
#define N 1000000
#define SortTest(sort,len) \
do { \
for(int i=0;i<len;i++)a[i]=s[i]; \
clock_t t=clock(); \
sort(a,len); \
printf(#sort" Use time:%ldms\n",clock()-t); \
}while(false)
int a[N],s[N];
int main()
{
srand((unsigned)time(NULL));
for (int i=0;i<N;i++)s[i]=rand();
printf("一万个数字对所有排序的测试：\n");
SortTest(InsertSort,10000);
SortTest(SelectSort,10000);
SortTest(BubbletSort,10000);
SortTest(CountSort,10000);
SortTest(QuickSort,10000);
SortTest(HeapSort,10000);
SortTest(ShellSort,10000);
SortTest(MergeSort,10000);
printf("\n100万个数字，对高级排序的测试：\n");
SortTest(CountSort,N);
SortTest(QuickSort,N);
SortTest(HeapSort,N);
SortTest(ShellSort,N);
SortTest(MergeSort,N);
return 0;
}
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include <ctime>
#include <iostream>
using namespace std;
#define SWAP(i,j) {int t=(i);(i)=(j);(j)=t;}
//插入排序
void InsertSort(int*a,int len)
{
for (int i=1;i<len;i++)
{
int j=i,x=a[i];
while (j && a[j-1]>x)a[j]=a[j-1],j--;
a[j]=x;
}
}
//选择排序
void SelectSort(int*a,int len)
{
for (int i=1,j,k;i<len;i++)
{
for (j=i,k=i-1;j<len;j++)
if (a[j]<a[k])k=j;
if (k>=i)SWAP(a[i-1],a[k]);
}
}
//冒泡排序
void BubbletSort(int*a,int len)
{
for (bool bSwap=true;bSwap;len--)
{
bSwap=false;
for (int j=1;j<len;j++)
if (a[j-1]>a[j]){SWAP(a[j-1],a[j]);bSwap=true;}
}
}
//计数排序
void CountSort(int*a,int len)
{
int c[RAND_MAX+1]={0};
for (int i=0;i<len;i++)c[a[i]]++;
for (int i=RAND_MAX;i>=0;)
if (c[i])a[--len]=i,c[i]--; else i--;
}
//堆调整
void HeapAdjust(int *a,int root,int len)
{
int child,x=a[root];
while (child=root<<1|1,child<len)
{
if (child<len-1 && a[child]<a[child+1])child++;
if (x<a[child]){a[root]=a[child];root=child;}
else break;
}
a[root]=x;
}
//堆排序
void HeapSort(int*a,int len)
{
for (int i=len/2-1;i>=0;i--)
HeapAdjust(a,i,len);
while (--len)
{
SWAP(a[0],a[len]);
HeapAdjust(a,0,len);
}
}
//归并
void Merge(int*a,int center,int len)
{
int *tmp=new int[len+2];
for (int i=0;i<center;i++)tmp[i]=a[i];
for (int i=center+1;i<=len;i++)tmp[i]=a[i-1];
tmp[center]=tmp[len+1]=INT_MAX;
for (int i=0,j=center+1,k=0;k<len;k++)
a[k]=tmp[(tmp[i]<tmp[j]?i:j)++];
delete[] tmp;
}
//归并排序
void MergeSort(int*a,int len)
{
if (len>1)
{
int c=len/2;
MergeSort(a,c);
MergeSort(a+c,len-c);
Merge(a,c,len-c);
}
}
//划分
int Partition(int*a,int len)
{
int x=a[--len],i=-1;
for (int j=0;j<len;j++)
if (a[j]<x){i++;SWAP(a[i],a[j]);}
SWAP(a[i+1],a[len]);
return i+1;
}
//快速排序
void QuickSort(int*a,int len)
{
if (len > 0)
{
int q=Partition(a,len);
if (q<len-q)
{
QuickSort(a,q);
QuickSort(a+q+1,len-q-1);
}
else
{
QuickSort(a+q+1,len-q-1);
QuickSort(a,q);
}
}
}
//希尔插入
void ShellInsert(int*a,int inc,int len)
{
for (int i=inc;i<len;i+=inc)
{
int j=i,x=a[i];
while (j>0 && a[j-inc]>x)a[j]=a[j-inc],j-=inc;
a[j]=x;
}
}
//插入式希尔排序
void ShellSort(int*a,int len)
{
int inc=len;
do
{
inc=inc/3+1;
for (int s=0;s<inc;s++)
ShellInsert(a-s,inc,len+s);
}
while (inc>1);
}
#define N 1000000
#define SortTest(sort,len) \
do { \
for(int i=0;i<len;i++)a[i]=s[i]; \
clock_t t=clock(); \
sort(a,len); \
printf(#sort" Use time:%ldms\n",clock()-t); \
}while(false)
int a[N],s[N];
int main()
{
srand((unsigned)time(NULL));
for (int i=0;i<N;i++)s[i]=rand();
printf("一万个数字对所有排序的测试：\n");
SortTest(InsertSort,10000);
SortTest(SelectSort,10000);
SortTest(BubbletSort,10000);
SortTest(CountSort,10000);
SortTest(QuickSort,10000);
SortTest(HeapSort,10000);
SortTest(ShellSort,10000);
SortTest(MergeSort,10000);
printf("\n100万个数字，对高级排序的测试：\n");
SortTest(CountSort,N);
SortTest(QuickSort,N);
SortTest(HeapSort,N);
SortTest(ShellSort,N);
SortTest(MergeSort,N);
return 0;
}
[[it] 本帖最后由 StarWing83 于 2008-7-7 17:46 编辑 [/it]]
