免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 5390 | 回复: 34

[函数] 请教大家一个关于快速排序的问题。 [复制链接]

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 14:34 |显示全部楼层
库里面自带的 qsort为 :

void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

我想问的是,如果对于内建的类型,比如int/char/long/double之类的,能不能不用定义那个比较函数 ?因为那个比较函数调用的非常频繁,这样效率会低很多的。我自己写了一个qsort比库里面那个非常之多,我觉得应该是库自带的那个qsort每次都调用fcmp这个函数进行比较带来的开销。
谢谢 。

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 20:35 |显示全部楼层
怎么一个人都没有的 ??

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2012-12-10 20:49 |显示全部楼层
这个不行啊,qsort不知道类型噬。

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 21:02 |显示全部楼层
回复 3# folklore


    内建的那些类型 直接用 > <号就行了啊。又不是struct这些 。如果每次都要调用那个比较函数 速度非常慢 。

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2012-12-10 21:08 |显示全部楼层
qsort,你自己直接写个不就行了

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 21:11 |显示全部楼层
其实没慢多少,你就别操心了

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 21:29 |显示全部楼层
回复 6# crazyhadoop

慢很、 非常多、慢 N倍。。。刚测试完。100W的数据,T1是我自己写的,T2是直接掉系统的。1000W相差更大。我写那个都没经过优化。因为qsort起码有2个地方是可以优化的。

inpput size:1000003
input times:10
t1 = 0.713seconds
t2 = 2.242seconds

t1 = 0.721seconds
t2 = 2.231seconds

t1 = 0.718seconds
t2 = 2.234seconds

t1 = 0.716seconds
t2 = 2.294seconds

t1 = 0.71seconds
t2 = 2.281seconds

请按任意键继续. . .
   

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 21:32 |显示全部楼层
回复 5# cokeboL


我是自己写了。因为我记得Qsort有2个地方是可以优化的,我想看我写的没有优化过的 跟系统的有优化的 性能差多少,没想到系统的那个比我写的还慢很多...估计是因为每次都调用哪个cmp函数的开销。所以想问下,对于这种内建的类型,完全不需要那个比较函数啊 ,能不能不定义。(或者说 不使用)

   

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 21:32 |显示全部楼层
回复 7# sublx


    把你的代码传上来看一下撒

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 21:39 |显示全部楼层
  1. int partition(int *array, int low, int high)
  2. {
  3.         int prov = array[low];
  4.         while(low < high)
  5.         {
  6.                 while(low < high && array[high] >= prov) high--;
  7.                 array[low] = array[high];
  8.                 while(low < high && array[low] <= prov) low++;
  9.                 array[high] = array[low];
  10.         }
  11.         array[low] = prov;
  12.         return low;
  13. }

  14. void qsort(int *array, int low, int high)
  15. {
  16.         if (low < high)
  17.         {
  18.                 int p = partition(array, low, high);
  19.                 qsort(array, low, p - 1);
  20.                 qsort(array, p + 1, high);
  21.         }
  22. }



  23. int num;
  24.         cout << "inpput size:";
  25.         cin >> num;
  26.         int times = 0;
  27.         cout << "input times:";
  28.         cin>>times;
  29.         int *a = new int[num];
  30.         int *b = new int[num];

  31.         clock_t m_start;
  32.         unsigned long t1, t2;

  33.         srand((unsigned int)time(NULL));
  34.        
  35.         int i = 0;
  36.         while(++i < times)
  37.         {
  38.                 for (int i = 0; i < num; ++i)
  39.                 {
  40.                         int temp = rand()%10000000;
  41.                         b[i] = a[i] = temp;
  42.                 }
  43.                 m_start = clock();
  44.                 //MergeSort(a, num);
  45.                 qsort(a, 0, num - 1);                //
  46.         //        qsort(a, num, sizeof(int), compare);//
  47.                 t1 = clock() - m_start;
  48.                 cout << "t1 = " << (double)(t1)/CLOCKS_PER_SEC << "seconds" <<endl;
  49.                 m_start = clock();
  50.                 //HeapSort(b, num);
  51.                 qsort(b, num, sizeof(int), compare);
  52.                 t2 = clock() - m_start;
  53.                 cout << "t2 = " << (double)(t2)/CLOCKS_PER_SEC << "seconds" <<endl;
  54.                 //show_array(a, num);
  55.                 //show_array(b, num);
  56.                 if (!isthesame(a, b, num)) break;
  57.                 else cout << "two arrays is the same.diff = " << (long)(t2 - t1) << endl;
  58.                 Sleep(300);
  59.         }
  60.         delete [] a;
  61.         delete [] b
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP