快排的实现

kingjo47

请各位帮忙看看 书上看到的快排 想自己实现出来 quicksort是书上的 别的自己写的 还有printf都是自己写的 想看数组里到底都是写什么数

1. #include <assert.h>
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. int x[100];
   
7. 
   
8. void swap(int ai,int bi)
   
9. {
   
10.         int temp;
    
11.         if(x[ai] < x[bi])
    
12.                 return ;
    
13.         else {
    
14.                 temp = x[ai];
    
15.                 x[ai] = x[bi];
    
16.                 x[bi] = temp;
    
17.         }
    
18. }
    
19. 
    
20. int randint(int s,int e)
    
21. {
    
22.         printf("s:%d\n",s);
    
23.         printf("e:%d\n",e);
    
24.         assert(s <= e);
    
25.         return rand()%(e - s);
    
26. }
    
27. 
    
28. void quicksort(int l,int u)
    
29. {
    
30.         int i,m,temp;
    
31.         if(l >= u) return ;
    
32.         printf("l %d\n",l);
    
33.         printf("u %d\n",u);
    
34.         temp = randint(l,u);
    
35.     swap(l,temp);
    
36.         m = l;
    
37.         printf("m:%d",m);
    
38.         for(i = l+1;i <= u; i++)
    
39.         {
    
40.                 if(x[i] < x[l])
    
41.                 swap(++m,i);
    
42.         }
    
43.         swap(l,m);
    
44.         quicksort(l,m-1);
    
45.         quicksort(m+1,u);
    
46. }
    
47. 
    
48. int main(int argc,char *argv[])
    
49. {
    
50.         int i = 0,m,j,n;
    
51.         int *pi;
    
52.         char a;
    
53.         printf("input number of data : exp 2 5 6 8 enter\n");
    
54.     while(scanf("%d",&x[i++]),(a = getchar()) != '\n')
    
55.       ;
    
56.         pi = x;
    
57.         //x[i+1] = '\0';
    
58.         for(j = 0;j < i; j++){
    
59.         printf("%d,",pi[j]);
    
60.         }
    
61.         printf("\n%d",sizeof(x));
    
62.         printf("\n%d",sizeof(pi));
    
63.     m = sizeof(pi)/sizeof(*pi);
    
64.         n = sizeof(x)/sizeof(*x);
    
65.         printf("\n%d",m);
    
66.         printf("\n%d",n);
    
67.         m = i;
    
68.         quicksort(0,m);
    
69.         for(i = 0;i < m;i++)
    
70.         {
    
71.            printf("%d,",x[i]);
    
72.         }
    
73.         getchar();
    
74.         return 0;
    
75. }

复制代码

kingjo47

上面是我自己弄错了 请看看下面的这个 最后一次把顺序乱了 帮忙看一下问题在哪儿

1. #include <assert.h>
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. int x[100];
   
7. 
   
8. void swap(int ai,int bi)
   
9. {
   
10.         int temp;
    
11.         if(x[ai] < x[bi])
    
12.                 return ;
    
13.         else {
    
14.                 temp = x[ai];
    
15.                 x[ai] = x[bi];
    
16.                 x[bi] = temp;
    
17.         }
    
18. }
    
19. 
    
20. int randint(int s,int e)
    
21. {
    
22.         printf("s:%d\n",s);
    
23.         printf("e:%d\n",e);
    
24.         assert(s <= e);
    
25.         return rand()%(e - s);
    
26. }
    
27. 
    
28. void quicksort(int l,int u)
    
29. {
    
30.         int i,m,temp;
    
31.         if(l >= u) return ;
    
32.         printf("l x[%d] %d\n",l,x[l]);
    
33.         printf("u x[%d] %d\n",u,x[u]);
    
34.         temp = randint(l,u);
    
35.     swap(l,temp);
    
36.         m = l;
    
37.         printf("m:%d\n",m);
    
38.         for(i = l+1;i <= u; i++)
    
39.                 if(x[i] < x[l])
    
40.                         swap(++m,i);
    
41.         swap(l,m);
    
42.         quicksort(l,m-1);
    
43.         quicksort(m+1,u);
    
44. }
    
45. 
    
46. int main(int argc,char *argv[])
    
47. {
    
48.         int i = 0,m,j,n;
    
49.         int *pi;
    
50.         char a;
    
51.         printf("input number of data : exp 2 5 6 8 enter\n");
    
52.     while(scanf("%d",&x[i++]),(a = getchar()) != '\n')
    
53.       ;
    
54.         pi = x;
    
55.         //x[i+1] = '\0';
    
56.         for(j = 0;j < i; j++){
    
57.         printf("%d,",pi[j]);
    
58.         }
    
59.         printf("\nx :%d",sizeof(x));
    
60.         printf("\npi :%d",sizeof(pi));
    
61.     m = sizeof(pi)/sizeof(*pi);
    
62.         n = sizeof(x)/sizeof(*x);
    
63.         printf("\nm %d",m);
    
64.         printf("\nn %d\n",n);
    
65.         m = i - 1;
    
66.         quicksort(0,m);
    
67.         for(j = 0;j < i;j++)
    
68.         {
    
69.            printf("x[%d] %d\t,",j,x[j]);
    
70.         }
    
71.         getchar();
    
72.         return 0;
    
73. }

复制代码

taps122

记得俺曾写过 C 版快速排序程序，代码很简短的。不过很奇怪，Visual C++6 和 Dev CPP 编译出来的 exe 运行速度竟然差很大：前者编译出来的 exe 运行时间约是后者的 1.3-1.5倍

egmkang

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

复制代码

OwnWaterloo

回复 4# egmkang

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

kingjo47

egmkang 发表于 2012-08-09 23:55

能说的详细点吗 没看懂

egmkang

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 []     = []  空的集合,返回就是空

kingjo47

egmkang 发表于 2012-08-10 09:18
这个是递归实现的qsort,代码相当容易看懂.
划分就是,针对一个集合A,取一个元素p,把小于p的移到p的左边 ...

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

egmkang

kingjo47 发表于 2012-08-10 09:36
我说的是上面这个quicksort函数不能正确排序 不知道哪儿错了 这个函数逻辑是没有错的 但就是不知道哪儿的 ...

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

kingjo47

谁能帮我看看 先谢谢了 自己跟踪数组里数据 递归几回就会发生一些情况 里面数据意外变了