| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4438 人关注过本帖, 8 人收藏
标题:[原创]各种排序方法总结【2008年7月7日更新】
只看楼主 加入收藏
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
结帖率:90%
收藏(8)
 问题点数:0 回复次数:43 
[原创]各种排序方法总结【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;
}


[[it] 本帖最后由 StarWing83 于 2008-7-7 17:46 编辑 [/it]]
搜索更多相关主题的帖子: 排序 总结 
2008-05-10 15:57
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
顶一个.........

樱花大战,  有爱.
2008-05-10 16:04
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
看了你的qsort又学习了////

樱花大战,  有爱.
2008-05-10 16:04
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
支持一下,可否让我把代码搬回家

i like linux...
2008-05-10 16:05
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
我也要做一下总结才行了。

i like linux...
2008-05-10 16:07
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
现在快排已经改好了,使用的是CLRS上的方法……沮丧……
希尔排序使用的是中学者的递进方法,我原先使用是inc[k]=2^(len-k+1)+1的方法,但是发现没有中学者的快……Orz……
不打算写基数排序了。在不使用STL数据结构的情况下空间复杂度为O(d*n+k),对于n=10^6的规模无法忍受……

[[it] 本帖最后由 StarWing83 于 2008-5-12 04:08 编辑 [/it]]

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-05-10 16:15
走一圈
Rank: 1
等 级:新手上路
帖 子:156
专家分:0
注 册:2008-5-9
收藏
得分:0 
辛苦了 顶你个
2008-05-10 16:26
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
Star兄,没有基数排???

樱花大战,  有爱.
2008-05-10 16:28
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
翅膀你的电脑好好啊...我测试下...我好像要26****ms..学校机器太破啊...

学习需要安静。。海盗要重新来过。。
2008-05-10 16:32
雨中飛燕
Rank: 1
等 级:新手上路
帖 子:765
专家分:0
注 册:2007-10-13
收藏
得分:0 
好像没写Shell-Insert

[color=white]
2008-05-10 16:32
快速回复:[原创]各种排序方法总结【2008年7月7日更新】
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035353 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved