高手请进！谁能把这段算法最优化，双手送上100分

你的意思就是按照z从小到大的顺序排序temp吧
改变一下存储结构
如果MAXZ不大的话，建立一个链表（可以用CList或者CArray），声明这个链表的MAXZ个的数组，把每个元素按Z放入不同的链表中，就可以方便的遍历了
如果MAXZ范围很大，可以做一个十字链表，十字链表其实就是由链表组成的链表，一样可以完成你的优化
看一下数据结构或者使用MFC的CList或者用STL的list都很容易实现嘻嘻 100分

原程序中用到的是链表，我只是为了讲述方便所以写成一个结构体
链表长度有时大有时小，最大几百，最小几十
而且成员不只一个Z，还有好多
也就是说现在要不改变链表的排序
有时按X，有时按Y来按顺序输出还说明一点是WIN32开发，不能使用MFC
100分不好拿的，花点心思想想吧
不限时间，什么时候想出办法了什么时候结分

kao，你小子不先把问题说清楚别人能咋办！在我的程序里是这样实现的，先排序，再遍历
typedef struct temp
{
         ……………………//其它数据
int ID;
         int x;
         int y;
int z;
}TEMP;typedef struct long_sort_index//长整型值排序索引
{
short iIndex;
long lData;
}SORT_INDEX;
//以下两个数组的空间可以根据最大容量用new的方式动态创建，为了方便，先这样写
TEMP structarray[100];
SORT_INDEX SortIndex1[100];
//当你需要按照比如说按照y来排序的话，
for(i=0;i<100;i++)
{
SortIndex1[i].iIndex=structarray[i].ID;
SortIndex1[i].lData=structarray[i].y;
}
//通过下面的函数排序上面的索引
SortIndex(SortIndex,100,0,100);//排序完之后，根据索引数组的iIndex访问结构体数组，就OK啦
//排序索引
/*
void SortIndex(SORT_INDEX *pIndex,int iIndexNum,int iSortMode,int iResultNum)
参数： SORT_INDEX *pIndex 排序索引
int iIndexNum 索引数目
int iSortMode 排序列(升序和降序)
int iResultNum 需要结果数目
返回值：无
*/
void SortIndex(SORT_INDEX *pIndex,int iIndexNum,int iSortMode,int iResultNum)
{
int i=0,j=0,k=iIndexNum-1;
SORT_INDEX a;
if(iResultNum<iIndexNum-1)
k=iResultNum;
for(i=0;i<k;i++)
{
for(j=i+1;j<iIndexNum;j++)
{
if(((pIndex[i].lData>pIndex[j].lData)&&(iSortMode==0))
||((pIndex[i].lData<pIndex[j].lData)&&(iSortMode==1)))
{
a=pIndex[i];
pIndex[i]=pIndex[j];
pIndex[j]=a;
}
}
}
return;
}
//对啦，顺便说一下，100分啊！！！
//上面这些是纯C的代码，如果用C++的话，可以用stl来实现一下速度可能会快一些，stl里面应该有关于快速排序的东东，没用过

kao，你小子不先把问题说清楚别人能咋办！在我的程序里是这样实现的，先排序，再遍历
typedef struct temp
{
         ……………………//其它数据
int ID;
         int x;
         int y;
int z;
}TEMP;typedef struct long_sort_index//长整型值排序索引
{
short iIndex;
long lData;
}SORT_INDEX;
//以下两个数组的空间可以根据最大容量用new的方式动态创建，为了方便，先这样写
TEMP structarray[100];
SORT_INDEX SortIndex1[100];
//当你需要按照比如说按照y来排序的话，
for(i=0;i<100;i++)
{
SortIndex1[i].iIndex=structarray[i].ID;
SortIndex1[i].lData=structarray[i].y;
}
//通过下面的函数排序上面的索引
SortIndex(SortIndex,100,0,100);//排序完之后，根据索引数组的iIndex访问结构体数组，就OK啦
//排序索引
/*
void SortIndex(SORT_INDEX *pIndex,int iIndexNum,int iSortMode,int iResultNum)
参数： SORT_INDEX *pIndex 排序索引
int iIndexNum 索引数目
int iSortMode 排序列(升序和降序)
int iResultNum 需要结果数目
返回值：无
*/
void SortIndex(SORT_INDEX *pIndex,int iIndexNum,int iSortMode,int iResultNum)
{
int i=0,j=0,k=iIndexNum-1;
SORT_INDEX a;
if(iResultNum<iIndexNum-1)
k=iResultNum;
for(i=0;i<k;i++)
{
for(j=i+1;j<iIndexNum;j++)
{
if(((pIndex[i].lData>pIndex[j].lData)&&(iSortMode==0))
||((pIndex[i].lData<pIndex[j].lData)&&(iSortMode==1)))
{
a=pIndex[i];
pIndex[i]=pIndex[j];
pIndex[j]=a;
}
}
}
return;
}
//对啦，顺便说一下，100分啊！！！
//上面这些是纯C的代码，如果用C++的话，可以用stl来实现一下速度可能会快一些，stl里面应该有关于快速排序的东东，没用过//排序索引

/*
减少循环的次数
楼主给不给分?
*/
#include <stdlib.h>
#include <stdio.h>#define MAX 100
#define MAXZ 10struct TEMP {
int ID;
int z;
int tag;//增加一个标志位,为1表示此数据尚未输出,为0则表示已输出
};int main(int argc, char* argv[])
{
struct TEMP * mytmp;
struct TEMP * mytmp2;
int i,j,z; mytmp=malloc(MAX);
if(!mytmp) return; mytmp2=mytmp;//两个指针指向同一段内存

for(i=0;i<MAX;i++){
mytmp[i].ID=i+1;
mytmp[i].z=rand()%MAXZ;
mytmp[i].tag=1;
}

for(z=0;z<MAXZ;z++)
{
j=0;
for(i=0;(i<MAX)&&(mytmp2[i].tag==1);i++){
if(mytmp2[i].z==z)
printf("%d ",mytmp2[i].ID);
else
mytmp[j++].z=mytmp2[i].z;//未输出的数据往数组前面移
}
mytmp[j].tag=0;//最后一个未输出数据的后一个数据标志为0
}
free(mytmp);
free(mytmp2);
return 0;
}

白天在公司上班，没时间调试
晚上有空把我和bluebohe(薄荷)和cernet(二黑)三个人的程序都调试了一下
全部是release版，分别输出5次所使用的时间（CPU频率）当MAX为100， MAXZ为10时
我的：260 260 261 260 263
薄荷：393 395 395 396 392
二黑：233 236 248 234 227当MAX为1000， MAXZ为100时
我的：87100 85249 86276 85207 86292
薄荷：99950 101403 99163 100836 101212
二黑：86757 86131 86652 87889 85702to bluebohe(薄荷) 你的算法不行啊，无论在空间在时间上都没有改善程序啊
to cernet(二黑) 你的代码并没有明显改善速度啊。特别MAX越大时，你的速度越接近我的啊还有谁能想出好的算法？

你把MAX改成100，MAXZ改成2^31-1试一下，看谁的快
我了解我做的程序，它的优势在于其扩展性好，根据你的如下提示
————————————————
而且成员不只一个Z，还有好多
也就是说现在要不改变链表的排序
有时按X，有时按Y来按顺序输出
————————————————我的程序是重用性最高的，只要一个数能转化成long值，就可以进行排序比较
而你们的程序仅仅当MAXZ比较小时才速度上得去
你想一下，你定义了MAXZ，当然还要定义MAXX、MAXY……是不，当它们各不相同的时候，怎么处理？一旦一个数的范围宽到整数的界限范围，怎么办？
再看一下速度测试
——————————————————————
当MAX为1000， MAXZ为100时
我的：87100 85249 86276 85207 86292
薄荷：99950 101403 99163 100836 101212
二黑：86757 86131 86652 87889 85702
————————————————————————不要太高，你把MAXZ提到200，我的程序应该还是这样的速度，而你们的程序的速度都要乘以2，是好是坏，是块是慢，你掂量一下——————————————————
to bluebohe(薄荷) 你的算法不行啊，无论在空间在时间上都没有改善程序啊
——————————————————就大多数情况而言，随着目前的硬件和软件水平的提高，一个程序的好坏不在于它的速度和浪费的内存，而在于它实现的功能、他的扩展性，dos和win2k两种操作系统的差别也在这里。所以，俺坚持俺的100分，呵呵

说说你这段代码不好的地方吧
排序确实可以加快链表输出
但重新对一个新的链表赋值浪费了太多的时间
另外我不是要对链表排序
是按顺序输出
难道排完了然后又比对一遍？
if(SortIndex1[i].iIndex==structarray[i].ID){
cout<<structarray[i].ID;
cout<<structarray[i].x;
cout<<structarray[i].y;
.........................}
别说把新结构体也加成员：）
我现在不要扩展性，单纯追求速度
循环输出这一段代码在我的程序每秒种要跑好几十次
所以速度在这里尤为重要

我没有排序链表，我只是排序我的结构体索引
怎么使用代码没告诉你你就没想到？哪用什么再对比一遍，逐个输出就可以了
for(i=0;i<MAXZ;i++)
{
cout<<structarray[SortIndex1[i].iIndex].ID;
cout<<structarray[SortIndex1[i].iIndex].x;
}
如果你用链表方式组织数据，那你需要改动成为数组方式，这样子才可以随机访问。
你的那种方式真的不可取，MAXZ一旦大一点，你就会碰到无法逾越的鸿沟，当然，如果数据范围只有0和1两个的话或者比数据总数少4/5以上我承认你的快

你看看是按你的意思写的吧
你如果能在三个程序中你的输出时间最快
马上结分int main(int argc, char* argv[])
{
__int64 start_time,end_time;
QueryPerformanceCounter((LARGE_INTEGER*)&start_time);
TEMP structarray[MAX];
int i; for(i=0;i<MAX;i++){
structarray[i].ID=i+1;
structarray[i].z=rand()%MAXZ;
}
SORT_INDEX SortIndex1[MAX]; for(i=0;i<MAX;i++)
{
SortIndex1[i].iIndex=i;
SortIndex1[i].lData=structarray[i].z;
} SortIndex(SortIndex1,100,0,100); for(i=0;i<MAX;i++)
{
cout<<structarray[SortIndex1[i].iIndex].ID;
}
cout<<"\n";

QueryPerformanceCounter((LARGE_INTEGER*)&end_time);
cout<<double(end_time-start_time) ;//(double)freq;
return 0;
}

牛*人物，I like!!帮你们up一下，不要分

我承认，如果MAXZ小，我的程序速度没你们快。这就是我的结论

#include <stdlib.h>
#include <stdio.h>
#define MAX 100
#define MAXZ 10
struct TEMP {
int ID;
int z;
};typedef struct TEMP_LIST_STRUCT
{
struct TEMP_LIST_STRUCT *next;
struct TEMP *temp;
}TEMP_LIST;int main(int argc, char* argv[])
{
struct TEMP mytmp[MAX];
int i,z;
TEMP_LIST* list[MAXZ];
TEMP_LIST list_buffer[MAX];
TEMP_LIST *cur; memset(list, 0, sizeof(list));

for(i=0;i<MAX;i++){
mytmp[i].ID=i+1;
mytmp[i].z=rand()%MAXZ;
}

for(i = 0; i < MAX; i++)
{
if(list[mytmp[i].z] == NULL)
{
list_buffer[i].next = NULL;
list_buffer[i].temp = &mytmp[i];
list[mytmp[i].z] = &list_buffer[i];
}
else
{
list_buffer[i].next = list[mytmp[i].z];
list_buffer[i].temp = &mytmp[i];
list[mytmp[i].z] = &list_buffer[i];
}
}
for(i = 0; i < MAXZ; i++)
{
cur = list[i];
while(cur != NULL)
{
printf("id = %d z = %d\n",cur->temp->ID, cur->temp->z);
cur = cur->next;
}
}

/*
for(z=0;z<MAXZ;z++)
for(i=0;i<MAX;i++){
if(mytmp[i].z==z)
printf("%d ",mytmp[i].ID);
}
*/
return 0;
}

这个程序有局限性，不过你没给定MAX和MAXZ的范围，属于出题过失

MAX 取 100-500
MAXZ 取 0-20
速度最优化优先

to bluebohe(薄荷) 别总拿一段代码出来说，不是不认同你的算法，确实不错，不过速度在这确实体现不出来，还不如花点时间再想个更好的算法
to hljzy() 你的算法不错，比我的快一点，比cernet(二黑)的慢一点，要我选择我更会选择你的，不过为什么速度还是不是第一，难道100分注定是给cernet(二黑)？？？
希望更多的高手参与进来帮忙想

随便请教一下，你们是通过什么方法知道
——————————————————————
当MAX为1000， MAXZ为100时
我的：87100 85249 86276 85207 86292
薄荷：99950 101403 99163 100836 101212
二黑：86757 86131 86652 87889 85702
————————————————————————
是通过软件吗？还是vc纸带的功能

__int64 start_time,end_time;
QueryPerformanceCounter((LARGE_INTEGER*)&start_time);
...............
QueryPerformanceCounter((LARGE_INTEGER*)&end_time);
cout<<double(end_time-start_time);我是这样看的

这个问题其实很简单，可以用桶式排序算法来作。
楼主的算法的时间复杂度为：MAX*MAXZ,使用桶样式可将时间复杂度降为 MAX *2,下面是代码。
// csdn_answer.cpp : Defines the entry point for the console application.
//#include <stdlib.h>
#include <stdio.h>
#include <string.h>#define MAX 100
#define MAXZ 10struct TEMP {
int ID;
int z;
};struct Bucket_ST
{
int total;
int beg;
};//该排序算法基于桶式排序算法，该函数的时间复杂度为 len * 2
void Sort( const TEMP src[], TEMP tag[], Bucket_ST buckArr[],int len,int buckLen )
{
int i;

memset(buckArr,0,sizeof(struct Bucket_ST)*buckLen); for (i=0;i<len;i++)
buckArr[src[i].z].total++;

for (i=1;i<buckLen;i++)
buckArr[i].beg = buckArr[i-1].beg+buckArr[i-1].total; // 将src 进行桶式排序，排序后的结果存储到 tag
memset(tag,0, sizeof(struct TEMP)*len);
for (i=0;i<len;i++)
{
int idx= buckArr[ src[i].z].beg;
tag[idx]= src[i];
buckArr[ src[i].z].beg=idx+1;
}
}
int main(int argc, char* argv[])
{
TEMP mytmp[MAX];
TEMP mytmp2[MAX];

struct Bucket_ST bucketArr[MAXZ]; int i;

for(i=0;i<MAX;i++)
{
mytmp[i].ID=i+1;
mytmp[i].z=rand()%MAXZ;
}

Sort( mytmp, mytmp2, bucketArr,MAX,MAX );

//for(z=0;z<MAXZ;z++)
//for(i=0;i<MAX;i++){
// if(mytmp[i].z==z)
// printf("%d ",mytmp[i].ID);
// }
for (i=0;i<MAX;i++)
{
printf("%d ,%d,\n",mytmp2[i].ID,mytmp2[i].z);
}
return 0;
}

所有的程序都输出了100次
输出时间是一样的
不信你可以把
QueryPerformanceCounter((LARGE_INTEGER*)&end_time);
cout<<double(end_time-start_time);
这句放在输出的前面
之所以用了算法还慢是因为大量的比较，赋值造成的
例如 liangbch(宝宝)的代码
for (i=0;i<len;i++)
{
    int idx= buckArr[ src[i].z].beg;
    tag[idx]= src[i];
    buckArr[ src[i].z].beg=idx+1;
}
虽然只遍历一次，但每次做了5件事
取src[i].z ，作为下标取buckArr[].beg值，再作下标给tag[]赋值，再把buckArr[].beg加1而我的代码虽然遍历了10次，但每次只做一件事
if(mytmp[i].z==z)话说回来，liangbch(宝宝)的算法的确不错
以前没见过这个算法，学习学习
而且速度也hljzy() 一样
再等几天看还有没有人有别的算法
没有的话就做结案陈词了

我分析过printf 的代码(vc 6.0版本）,他最终调用WriteFile 函数输出到控制台。但是在转化变量到字符串时，包含了大量的分析，且这个函数的调用层次也比较多。所以printf函数占用了很大的cpu时间，建议在做数据测试时，对运算和输出分段测试，这样才能知道算法的快慢，快多少倍，这样的比较才公平。

那你再分析一下cout<<
看看调用100次cout会不会时间不一样长
你可以把上面4个代码都自己编译一遍
随便你输不输出
要和我的有出入
我100分给你

1。楼主，我将这4个算法整理一下，发现屏幕输出占用比例很大的时间，实在是难分高下。
  2。我将屏幕输出改为输出到文件，输出的时间就减小了，并且将 MAX 设为1000，MAXZ设为100，这样算法的好坏就出来了。下面为输出结果。（第1种：搂主，第二种：bluebohe(薄荷) ，第3种：cernet(二黑) 第4种:liangbch（宝宝)
排序时间:
第1种:       0       0       0       0       0       0       0       0
第2种:   60881   30952   30565   31123   30108   31046   30231   30766
第3种:       0       0       0       0       0       0       0       0
第4种:     400     257     262     256     260     259     257     263输出时间:
第1种:   36992   41389   40344   37370   37359   38740   37419   41030
第2种:   37127   37819   35708   35485   34948   34798   39050   38119
第3种:   37265   40609   37930   37810   37854   37999   47340   37765
第4种:   38035   36049   34835   35069   34956   35650   38168   38621
  3。如果你想亲自测试一下的话，请将e_mail留下，我将代码发送给你，你自己测试一下吧。

sorry,我比较菜，但是我觉点这样也会加快一点速度。
按楼主的程序，我在VC.net中
改变 for(z=0;z<MAXZ;z++)
for(i=0;i<MAX;i++)
的循环顺序.使之变为
for(i=0;i<MAX;i++)
for(z=0;z<MAXZ;z++)
这样速度也会加快一点。
void CokDlg::OnBnClickedButton1()
{
LARGE_INTEGER  litmp ;
LONGLONG  QPart1,QPart2 ;
double  dfMinus, dfFreq, dfTim ; // 获得计数器的时钟频率
QueryPerformanceFrequency(&litmp);
dfFreq = (double)litmp.QuadPart;
// 获得初始值
QueryPerformanceCounter(&litmp);
QPart1 = litmp.QuadPart;//以下是要测试代码所用的时间
TEMP mytmp[MAX];
int i,z;

for(i=0;i<MAX;i++){
mytmp[i].ID=i+1;
mytmp[i].z=rand()%MAXZ;
}

for(i=0;i<MAX;i++)
for(z=0;z<MAXZ;z++)
{
if(mytmp[i].z==z)
printf("%d\n ",mytmp[i].ID);
}// 获得终止值
QueryPerformanceCounter(&litmp);
QPart2 = litmp.QuadPart;
dfMinus = (double)(QPart2 - QPart1);
dfTim = dfMinus / dfFreq;
TRACE("%f\n",dfTim);
// 获得对应的时间值
}

MAX定义为10000
MAXZ定义为1000时
按楼主的方法得到:
0.190931
0.190791
0.206632
0.192938
0.194696我改动循环的内外环后得到：
0.122579
0.124961
0.125161
0.124844
0.125154我按5次按钮的。
不知我的方法是否有一点用，我是初学的。请多指教。

To liangbch(宝宝) ：
我还是觉得把结果放在内存里面要比输到文件中干扰小一些。

我建议还是正常的输出
因为VC会自己优化代码
当VC认为没有输出时不知道他把代码优化成什么了
也许不做任何事
就像宝宝的测试出现
第1种: 0 0 0 0 0 0 0 0

vc的优化自然我是知道的，如果一段复杂的计算过程（包括循环)计算出来的值没有使用，那么，release 版本就不会对这段代码进行编译。

请支持一下
http://www.1931-9-18.com
http://sign.1931-9-18.org/gaspay_sign.asp

晕,这么多人研究算法,殊不知这个程序中最影响速度和效率的是printf("%d ",mytmp[i].ID);不知道?自己去想吧
所以最好把你们的算法和printf("%d ",mytmp[i].ID);分开
用多线程加信号量可以解决这个最大的效率问题

楼主，不输出到屏幕并不是不输出，可以先用数组保存结果在内存中，计时之后在把内存中的结果输出，你可以再计时一次看，printf看看是计算时的多少倍？
我的机器上不知道是不是没有 liangbch(宝宝) 的快，还是他的代码有问题？
楼主的算法在我的机器上的计算时间是：1862，包括输出时间则是：659385

hljzy给出的代码性能相比之下令人惊讶：129，比二黑的快上将近10倍！，比楼主得快上14倍多！但是首先说明一点，我没有对程序的逻辑正确性进行验证，这个工作留给搂主自己吧。

我把上面几段代码都从新调整了一下
按大家的意思先输出到内存，比较速度再输出
二黑的代码我仔细看了看
破坏了本来的顺序，违背了题意
所以没参与比较
比较结果还是和以前一样
由快到慢依次为
hljzy() > liangbch(宝宝) > 我的 > bluebohe(薄荷) 大家可以把全部代码下载下来自己测试
如果测试和我的有出入请指出
http://17173.finestar.net/time.rar

楼主最后测试的排名结果跟我测试的一致。
不过，hljzy()和liangbch(宝宝)的代码速度由于非常快，所以很难比较出绝对的结果。
因为，liangbch(宝宝)的代码有函数调用开销，在函数内部测试要比外部测试的耗时少30多，而且做memset也会花去不少，所以在这个数量级（MAX 设为1000，MAXZ设为100）比较不公平。因为函数调用和memset只运行一次，不应该包含在算法当中。或者加大测试负荷，或者比较时间复杂度才公平。
仔细看了一下他们的代码，我认为hljzy()和liangbch(宝宝)的应该是一样的算法，只是实现方式不一样，因此，我觉得他们的算法持平。

错，他们的代码各有千秋
hljzy()的是一个MAXZ长的list
list的每个结点指向当前z值的list_buffer
list_buffer的next指向下一个为z值的list_buffer
就像储存链表头的链表,而且不开辟新的内存,很理想而liangbch(宝宝)的是根据z值来取buckArr[].beg的值
根据这个值来确定存在新的排序中的位置
从而排出一个新的按顺序输出的结构
唯一不好的是产生了一个和原来结构相同大小的mytmp2[MAX]

******************************************************#
#    如果你想优可读性,已经很好了!                       #
#    如果只想优化运行速度,请用二叉树+regist变量+asm{}   #
#                                                    #
#    代码教科书有的是,我就不给出了!                    #
*****************************************************#

给段堆排序的吧：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX 100
#define MAXZ 10
struct TEMP {
int ID;
int z;
};inline void PushDown(TEMP C[],int start, int end)
{
  long i,j;
  TEMP x;
  x.z = C[start].z;
  x.ID = C[start].ID;
  i = start;
  j = i * 2;
  while (j <= end){
    if (j < end && C[j].z > C[j+1].z)
      j++;
    if (x.z > C[j].z){
      C[i].ID = C[j].ID;
      C[i].z = C[j].z;
      i = j;
      j *= 2;
    } else
      break;
  }
  C[i].ID = x.ID;
  C[i].z = x.z;
}int main(int argc, char* argv[])
{
TEMP C[MAX];
int i,z;
srand(time(NULL));
for(i=0;i<MAX;++i){
C[i].ID=i+1;
C[i].z=rand()%MAXZ;
    }

  int last = MAX-1;
  int t;

  for (i = last/2; i >= 0; --i)
    PushDown(C, i, last);
  for (i = last; i > 0; --i){
    printf("%d ", C[0].ID);
    //Swap
    t = C[0].ID;
    C[0].ID = C[i].ID;
    C[i].ID = t;

    t = C[0].z;
    C[0].z = C[i].z;
    C[i].z = t;

    PushDown(C, 0, i-1);
  }
}

给段排序算法效率的比较的程序：
随机生成MaxSize = 10000个数据，运行冒泡排序、选择排序、插入排序、希尔排序、合并排序、快速排序和堆排序，统计各个排序算法的运行时间。在一般情况下,排序算法的效率是:冒泡 < 选择 < 插入 < 希尔(合并,堆) < 快速排序,其中快速排序在实际使用中的效率最好.上述几种排序算法都是属于"比较类算法",也就是算法在最坏情况下,最优时间效率是O(NlogN).当然,遇到一些特殊情况,如果能够使用某些线性排序算法,那效率是最好的.
TC3.0下通过
#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
const int MaxSize = 10000;
int A[MaxSize];
void Initialize()
{
  int i;
  srand((unsigned) time(NULL));
  for (i = 0; i < MaxSize; i++)
    A[i] = rand();
}
void MakeBak(int C[])
{
  for (int i = 0; i < MaxSize; i++)
    C[i] = A[i];
}void Print(int C[])
{
  int i;
  for (i = 0; i < MaxSize; i++)
    printf("%d ", C[i]);
  printf("\n");
}void Swap(int *i, int *j)
{
  int temp;
  temp = *i;
  *i = *j;
  *j = temp;
}void BubbleSort(int C[], int start, int end)
{
  int i, j;
  for (i = start; i < end-1; i++)
    for (j = end-1; j > i; j--)
      if (C[j] < C[j-1])
Swap(&C[j], &C[j-1]);
}
void SelectionSort(int C[], int start, int end)
{
  int i,j,t;
  for (i = start; i < end-1; i++){
    t = i;
    for (j = i+1; j < end; j++)
      if (C[i] > C[j])
t = j;
    Swap(&C[i], &C[t]);
  }
}void InsertionSort(int C[], int start, int end)
{
  int i,j,t;
  for (i = start+1; i < end-1; i++){
    t = C[i];
    for (j = i-1; j >= start && C[j] > t; j--)
      C[j+1] = C[j];
    C[j+1] = t;
  }
}int Partition(int C[], int j, int r, int key)
{
  j--;
  r++;
  while (1){
    do j++; while (C[j] < key);
    do r--; while (C[r] > key);
    if (j < r)
      Swap(&C[j], &C[r]);
    else
      return r;
  }
}int Random(int i, int j)
{
  return rand() % (j-i+1) + i;
}
void Random_QuickSort(int C[], int j, int r)
{
  if (j < r){
    int p = Partition(C, j, r, C[Random(j,r)]);
    Random_QuickSort(C, j, p);
    Random_QuickSort(C, p+1, r);
  }
}void PushDown(int C[], int start, int end)
{
  long i,j;
  int x = C[start];
  i = start;
  j = i * 2;
  while (j <= end){
    if (j < end && C[j] < C[j+1])
      j++;
    if (x < C[j]){
      C[i] = C[j];
      i = j;
      j *= 2;
    } else
      break;
  }
  C[i] = x;
}void HeapSort(int C[], int start, int end)
{
  int i;
  for (i = end/2; i >= start; i--)
    PushDown(C, i, end);
  for (i = end; i > start; i--){
    Swap(&C[start], &C[i]);
    PushDown(C, start, i-1);
  }
}void ShellSort(int C[], int end)
{
  int i, p, j, m, t, k;
  int *d;
  t = floor(log(end) / log(2));
  d = (int *) malloc (t*sizeof(int));
  for (i = 0, k = 2; i < (int)t; i++, k *= 2)
    d[i] = k - 1;  for (i = t-1; i >= 0; i--){
    p = d[i];
    for (j = p; j < end; j++){
      k = C[j];
      for (m = j-p; m >= 0 && C[m] > k; m -= p)
C[m+p] = C[m];
      C[m+p] = k;
    }
  }
}void Merge(int C[], int bak[], int l, int m, int r)
{
  int i = l, j = m+1, k = l;
  while (i <= m && j <= r)
    if (C[i] <= C[j])
      bak[k++] = C[i++];
    else
      bak[k++] = C[j++];
  if (i > m)
    for (int q = j; q <= r; q++)
      bak[k++] = C[q];
    else
      for (int q = i; q <= m; q++)
bak[k++] = C[q];
}
void MergePass(int C[], int bak[], int s, int n)
{
  int i = 0;
  while (i <= n-2*s){
    Merge(C, bak, i, i+s-1, i+2*s-1);
    i = i + 2 * s;
  }
  if (i+s < n)
    Merge(C, bak, i, i+s-1, n-1);
  else
    for (int j = i; j < n; j++)
      bak[j] = C[j];
}
void NR_MergeSort(int C[], int n) //Not Recursion MergeSort
{
  int *bak = (int *) malloc (n*sizeof(int));
  int s = 1;
  while (s < n){
    MergePass(C, bak, s, n);
    s += s;
    MergePass(bak, C, s, n);
    s += s;
  }
}
/*
void MergeSort(..)
{
  if (left < right){
    int i = (left+right)/2;
    MergeSort(a, left, i);
    MergeSort(a, i+1, right);
    Merge(a,b,left,i,right); //Merge to Array b;
    Copy(a,b,left,right); //Copy back to Array a;
  }
}
*/
void main()
{
  struct time t1, t2;
  int C[MaxSize];
  clrscr();
  Initialize();  MakeBak(C);
  gettime(&t1);
  BubbleSort(C, 0 , MaxSize);
  gettime(&t2);
  printf("BublleSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);  MakeBak(C);
  gettime(&t1);
  SelectionSort(C, 0 , MaxSize);
  gettime(&t2);
  printf("SelectionSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);  MakeBak(C);
  gettime(&t1);
  InsertionSort(C, 0 , MaxSize);
  gettime(&t2);
  printf("InsertionSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);  MakeBak(C);
  gettime(&t1);
  ShellSort(C, MaxSize);
  gettime(&t2);
  printf("ShellSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);  MakeBak(C);
  gettime(&t1);
  NR_MergeSort(C, MaxSize);
  gettime(&t2);
  printf("NR_MergeSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);
  MakeBak(C);
  gettime(&t1);
  Random_QuickSort(C, 0 , MaxSize-1);
  gettime(&t2);
  printf("QuickSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);  MakeBak(C);
  gettime(&t1);
  HeapSort(C, 0 , MaxSize-1);
  gettime(&t2);
  printf("HeapSort running time is: %f\n",(t2.ti_hour-t1.ti_hour)*3600+
    (t2.ti_min-t1.ti_min)*60+t2.ti_sec-t1.ti_sec+(t2.ti_hund-t1.ti_hund)*0.01);//  Print(C);
}

从这里转贴的
http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.7442285

liangbch(宝宝)的改进了一下，比hljzy()还稍快一些，
在我的机器上是21ms : 22ms，没改之前是 23~24ms : 22ms
我加了随机种子，测试更公平一些
MAX=100，MAXZ=10// test3.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include <windows.h>
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>#define MAX 100
#define MAXZ 10struct TEMP {
int ID;
int z;
};struct Bucket_ST
{
int total;
int beg;
};//该排序算法基于桶式排序算法，该函数的时间复杂度为 len * 2
void  Sort( const TEMP  src[], int indexs[], Bucket_ST buckArr[],int len,int buckLen )
{
int i;

memset(buckArr,0,sizeof(struct Bucket_ST)*buckLen); for (i=0;i<len;i++)
buckArr[src[i].z].total++;

for (i=1;i<buckLen;i++)
buckArr[i].beg = buckArr[i-1].beg+buckArr[i-1].total; // 将src 进行桶式排序，排序后的结果存储到 tag
//memset(tag,0, sizeof(struct TEMP)*len);
for (i=0;i<len;i++)
{
int idx = buckArr[ src[i].z].beg;
//tag[idx] = src[i]; //其实这里没必要复制src的值，
indexs[idx] = i; //只需记录i的值做索引就行了，这样比复制src要快些
buckArr[ src[i].z].beg=idx+1;
}
}
int main(int argc, char* argv[])
{
srand( (unsigned)time( NULL ) ); //种随机种子 __int64    start_time,end_time;
QueryPerformanceCounter((LARGE_INTEGER*)&start_time); TEMP mytmp[MAX];
//TEMP mytmp2[MAX];

struct Bucket_ST  bucketArr[MAXZ]; int i;

for(i=0;i<MAX;i++)
{
mytmp[i].ID=i+1;
mytmp[i].z=rand()%MAXZ;
}

int indexs[MAX];
Sort( mytmp, indexs, bucketArr,MAX,MAXZ );

QueryPerformanceCounter((LARGE_INTEGER*)&end_time);

for (i=0;i<MAX;i++)
{
//cout<<mytmp2[i].ID<<" ";
cout<<mytmp[indexs[i]].ID<<" ";
}
cout<<"\n";
cout<<double(end_time-start_time); return 0;
}

如果加上这句，也是21-22ms
memset(indexs,0, sizeof(int)*len);

楼主，你是关心代码还是算法？hljzy()和liangbch(宝宝)的明明都是基于桶式排序排序的思想，实现的方式不一样而已，一个是用List来当桶，另一个用数组来当桶，有什么本质区别？

上面已经说过了，他们两的算法不一样
hljzy()做出来是
list[0]->list_buffer[0]->list_buffer[1]->NULL
list[1]->list_buffer[2]->......->list_buffer[i]->NULL
.......................................
list[9]->list_buffer[99]->NULL而liangbch(宝宝)的精华在于buckArr[i].beg
他判断z值的大小来知道存在桶中的位置
存一个后，下一个这个z值的数位置就在buckArr[i].beg+1的位置里
以此类推而且我的题目是最快者得100分
如果你对我个给分有异议，你可以再开张帖谈谈
看看大家的意见

不知楼主是否知道什么是桶式排序？不是非要用数组来当桶才叫桶式排序的。你说的那个所谓的“精华”根本就不能算是精华，它只不过是作为指向存储同一关键字的存储空间的指针。而hljzy() 用的是链表节点来指向存储同一关键字的存储空间。两种方式的不同点在于前者预先分配好所有的存储空间，需要预先做一次遍历来确定各关键字在存储空间中的位置；后者是边扫描边分配存储空间，需要做实时分配存储空间（性能瓶颈）然后挂到关键字链表上。
如果楼主仅仅追求的代码的速度最快而不是算法时间复杂度最低，那么可以用上各种技巧了（比如内嵌汇编之类的）。

事实上，由于 liangbch(宝宝)的代码的排序输出的数据结构正好是楼主所需要的，因此不存在hljzy() 需要把链表转换成数组消耗的内存Copy的代价。而实际应用中，根据具体情况，未必用数组的就比用链表的好。

调试易

高手请进！谁能把这段算法最优化，双手送上100分

解决方案 »