免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 5892 | 回复: 9

[算法] 快排的实现 [复制链接]

论坛徽章:
0
发表于 2012-08-09 13:06 |显示全部楼层
请各位帮忙看看 书上看到的快排 想自己实现出来 quicksort是书上的 别的自己写的 还有printf都是自己写的 想看数组里到底都是写什么数
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>

  5. int x[100];

  6. void swap(int ai,int bi)
  7. {
  8.         int temp;
  9.         if(x[ai] < x[bi])
  10.                 return ;
  11.         else {
  12.                 temp = x[ai];
  13.                 x[ai] = x[bi];
  14.                 x[bi] = temp;
  15.         }
  16. }

  17. int randint(int s,int e)
  18. {
  19.         printf("s:%d\n",s);
  20.         printf("e:%d\n",e);
  21.         assert(s <= e);
  22.         return rand()%(e - s);
  23. }

  24. void quicksort(int l,int u)
  25. {
  26.         int i,m,temp;
  27.         if(l >= u) return ;
  28.         printf("l %d\n",l);
  29.         printf("u %d\n",u);
  30.         temp = randint(l,u);
  31.     swap(l,temp);
  32.         m = l;
  33.         printf("m:%d",m);
  34.         for(i = l+1;i <= u; i++)
  35.         {
  36.                 if(x[i] < x[l])
  37.                 swap(++m,i);
  38.         }
  39.         swap(l,m);
  40.         quicksort(l,m-1);
  41.         quicksort(m+1,u);
  42. }

  43. int main(int argc,char *argv[])
  44. {
  45.         int i = 0,m,j,n;
  46.         int *pi;
  47.         char a;
  48.         printf("input number of data : exp 2 5 6 8 enter\n");
  49.     while(scanf("%d",&x[i++]),(a = getchar()) != '\n')
  50.       ;
  51.         pi = x;
  52.         //x[i+1] = '\0';
  53.         for(j = 0;j < i; j++){
  54.         printf("%d,",pi[j]);
  55.         }
  56.         printf("\n%d",sizeof(x));
  57.         printf("\n%d",sizeof(pi));
  58.     m = sizeof(pi)/sizeof(*pi);
  59.         n = sizeof(x)/sizeof(*x);
  60.         printf("\n%d",m);
  61.         printf("\n%d",n);
  62.         m = i;
  63.         quicksort(0,m);
  64.         for(i = 0;i < m;i++)
  65.         {
  66.            printf("%d,",x[i]);
  67.         }
  68.         getchar();
  69.         return 0;
  70. }
复制代码

论坛徽章:
0
发表于 2012-08-09 14:26 |显示全部楼层
上面是我自己弄错了 请看看下面的这个 最后一次把顺序乱了 帮忙看一下问题在哪儿
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>

  5. int x[100];

  6. void swap(int ai,int bi)
  7. {
  8.         int temp;
  9.         if(x[ai] < x[bi])
  10.                 return ;
  11.         else {
  12.                 temp = x[ai];
  13.                 x[ai] = x[bi];
  14.                 x[bi] = temp;
  15.         }
  16. }

  17. int randint(int s,int e)
  18. {
  19.         printf("s:%d\n",s);
  20.         printf("e:%d\n",e);
  21.         assert(s <= e);
  22.         return rand()%(e - s);
  23. }

  24. void quicksort(int l,int u)
  25. {
  26.         int i,m,temp;
  27.         if(l >= u) return ;
  28.         printf("l x[%d] %d\n",l,x[l]);
  29.         printf("u x[%d] %d\n",u,x[u]);
  30.         temp = randint(l,u);
  31.     swap(l,temp);
  32.         m = l;
  33.         printf("m:%d\n",m);
  34.         for(i = l+1;i <= u; i++)
  35.                 if(x[i] < x[l])
  36.                         swap(++m,i);
  37.         swap(l,m);
  38.         quicksort(l,m-1);
  39.         quicksort(m+1,u);
  40. }

  41. int main(int argc,char *argv[])
  42. {
  43.         int i = 0,m,j,n;
  44.         int *pi;
  45.         char a;
  46.         printf("input number of data : exp 2 5 6 8 enter\n");
  47.     while(scanf("%d",&x[i++]),(a = getchar()) != '\n')
  48.       ;
  49.         pi = x;
  50.         //x[i+1] = '\0';
  51.         for(j = 0;j < i; j++){
  52.         printf("%d,",pi[j]);
  53.         }
  54.         printf("\nx :%d",sizeof(x));
  55.         printf("\npi :%d",sizeof(pi));
  56.     m = sizeof(pi)/sizeof(*pi);
  57.         n = sizeof(x)/sizeof(*x);
  58.         printf("\nm %d",m);
  59.         printf("\nn %d\n",n);
  60.         m = i - 1;
  61.         quicksort(0,m);
  62.         for(j = 0;j < i;j++)
  63.         {
  64.            printf("x[%d] %d\t,",j,x[j]);
  65.         }
  66.         getchar();
  67.         return 0;
  68. }
复制代码

论坛徽章:
0
发表于 2012-08-09 21:47 |显示全部楼层
记得俺曾写过 C 版快速排序程序,代码很简短的。不过很奇怪,Visual C++6 和 Dev CPP 编译出来的 exe 运行速度竟然差很大:前者编译出来的 exe 运行时间约是后者的 1.3-1.5倍

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2012-08-09 23:55 |显示全部楼层
  1. quicksort :: Ord a => [a] -> [a]
  2. quicksort []     = []
  3. quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
  4.     where
  5.         lesser  = filter (< p) xs
  6.         greater = filter (>= p) xs
复制代码

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-10 00:09 |显示全部楼层
回复 4# egmkang

终于能看懂其他人写的haskell代码了。。。
想起以前被人丢一坨haskell代码看不懂,只能干瞪眼。。。哎。。。

论坛徽章:
0
发表于 2012-08-10 08:49 |显示全部楼层
egmkang 发表于 2012-08-09 23:55

能说的详细点吗 没看懂

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2012-08-10 09:18 |显示全部楼层
本帖最后由 egmkang 于 2012-08-10 09:18 编辑
kingjo47 发表于 2012-08-10 08:49
能说的详细点吗 没看懂


这个是递归实现的qsort,代码相当容易看懂.
划分就是,针对一个集合A,取一个元素p,把小于p的移到p的左边,大于p的移到p的右边
quicksort (p : xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

(p : xs)只是取数组的第一个元素当作p
lesser  = filter (< p) xs,   lesser就是在xs集合内取小于p的
greater = filter (>= p) xs,greater就是在xs集合内取大于等于p的

quicksort []     = []  空的集合,返回就是空

论坛徽章:
0
发表于 2012-08-10 09:36 |显示全部楼层
egmkang 发表于 2012-08-10 09:18
这个是递归实现的qsort,代码相当容易看懂.
划分就是,针对一个集合A,取一个元素p,把小于p的移到p的左边 ...

我说的是上面这个quicksort函数不能正确排序 不知道哪儿错了 这个函数逻辑是没有错的 但就是不知道哪儿的问题

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2012-08-10 09:40 |显示全部楼层
kingjo47 发表于 2012-08-10 09:36
我说的是上面这个quicksort函数不能正确排序 不知道哪儿错了 这个函数逻辑是没有错的 但就是不知道哪儿的 ...



先实现一个正确的划分吧....
我现在很懒,不愿意看代码,略微复杂的就不想看了

论坛徽章:
0
发表于 2012-08-10 11:35 |显示全部楼层
谁能帮我看看 先谢谢了 自己跟踪数组里数据 递归几回就会发生一些情况 里面数据意外变了
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP