[已解决]S1E32猴子排序问题

雨中漫步~

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. 
   
6. int in_order(int array[], int length);
   
7. void shuffle(int array[], int length);
   
8. void bogo_sort(int array[], int length);
   
9. 
   
10. int in_order(int array[], int length)
    
11. {
    
12.         int i = 0;
    
13. 
    
14.         while (array[i] <= array[i+1] && ++i < length - 1)
    
15.                 ;
    
16. 
    
17.         if (i == length - 1)
    
18.         {
    
19.                 return 1;
    
20.         }
    
21.         else
    
22.         {
    
23.                 return 0;
    
24.         }
    
25. }
    
26. 
    
27. void shuffle(int array[], int length)
    
28. {
    
29.         int index, temp, i;
    
30.         static int t1, t2;
    
31. 
    
32.         srand(t1);
    
33.         t1 = rand();
    
34. 
    
35.         t2 = time(NULL);
    
36.         srand(t1+t2);
    
37. 
    
38.         for (i = 0; i < length; i++)
    
39.         {
    
40.                 index = rand() % (length - i) + i;
    
41.                 if (index != i)
    
42.                 {
    
43.                         temp = array[i];
    
44.                         array[i] = array[index];
    
45.                         array[index] = temp;
    
46.                 }
    
47.         }
    
48. }
    
49. 
    
50. void bogo_sort(int array[], int length)
    
51. {
    
52.         while (!in_order(array, length))
    
53.         {
    
54.                 shuffle(array, length);
    
55.         }
    
56. }
    
57. 
    
58. int main(void)
    
59. {
    
60.         int array[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
    
61.         int i, length;
    
62.         time_t begin, end;
    
63. 
    
64.         begin = time(NULL);
    
65. 
    
66.         length = sizeof(array) / sizeof(array[0]);
    
67.         
    
68.                 bogo_sort(array, length);
    
69. 
    
70.         printf("排序后的结果是：");
    
71.         for (i = 0; i < length; i++)
    
72.         {
    
73.                 printf("%d ", array[i]);
    
74.         }
    
75.         putchar('\n');
    
76. 
    
77.         end = time(NULL);
    
78.         printf("总共耗时：%ld秒\n", end - begin);
    
79. 
    
80.         return 0;
    
81. }

复制代码

1. 
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. #include <stdlib.h>
   
5. 
   
6. int in_order(int array[], int length);
   
7. void shuffle(int array[], int length);
   
8. void bogo_sort(int a[], int n);
   
9. 
   
10. int in_order(int array[], int length)//判断洗牌后的数组中数字是否顺序排列
    
11. {
    
12.         int i = 0;
    
13.        
    
14.         while(array[i] < array[i+1] && ++i < length -1)
    
15.                 ;
    
16.                
    
17.         if (i == length - 1)
    
18.         {
    
19.                 return 1;
    
20.         }
    
21.         else
    
22.         {
    
23.                 return 0;
    
24.         }
    
25. }
    
26. 
    
27. void shuffle(int array[], int length)// 随机排序
    
28. {
    
29.         int index, temp, i;
    
30.                                
    
31.         srand(time(NULL));        //rand(time(NULL)) 获得随机数的间隔是 1 秒 1 次
    
32.        
    
33.         for (i = 0;i < length;i++)
    
34.         {
    
35.                 index = rand() % (length - i) + i;
    
36.                 if (index != i)
    
37.                 {
    
38.                         temp = array[index];
    
39.                         array[index] = array[i];
    
40.                         array[i] = temp;
    
41.                 }
    
42.         }
    
43. }
    
44. 
    
45. void bogo_sort(int array[], int length) //当与目标字符串一致时跳出循环
    
46. {
    
47.         while (!in_order(array, length))
    
48.         {
    
49.                 shuffle(array, length);
    
50.         }       
    
51. }
    
52. 
    
53. int main(void)
    
54. {
    
55.         int array[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
    
56.         int i, length;
    
57.         time_t begin, end;
    
58. 
    
59.         begin = time(NULL); //time：获取当前系统时间（UTC时间）的time_t值
    
60. 
    
61.         length = sizeof(array) / sizeof(array[0]);
    
62.         bogo_sort(array, length);
    
63. 
    
64.         printf("排序后的结果是：");
    
65.         for (i = 0; i < length; i++)
    
66.         {
    
67.                 printf("%d ", array[i]);
    
68.         }
    
69.         putchar('\n');
    
70. 
    
71.         end = time(NULL);
    
72.         printf("总共耗时：%ld秒\n", end - begin);
    
73. 
    
74.         return 0;
    
75. }

复制代码

请问这两个程序在dev C++中运行，为什么运行时间会这么长，运行很久都得不出结果？

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-10-8 20:40:59

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. 
   
5. void swap(void *a, void *b) {
   
6.     unsigned char *p = a;
   
7.     unsigned char *q = b;
   
8.     unsigned char tmp;
   
9.     tmp = *p;        
   
10.     *p = *q;         
    
11.     *q = tmp;        
    
12. }
    
13. 
    
14. void shuffle(void *x, int size_elem, int total_elem) {
    
15.     int i = total_elem - 1;            
    
16.     for(i ; i >= 0; --i) {
    
17.         int r = rand() % (i+1);
    
18.         swap(x + r*size_elem, x + i*size_elem);
    
19.     }                 
    
20. }
    
21. 
    
22. int main(int argc, char *argv[]) {
    
23.     time_t begin, end;
    
24.     begin = time(NULL);
    
25.     srand((unsigned)time(NULL));
    
26.     int l[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
    
27.     int n;
    
28.     n = sizeof(l)/sizeof(l[0]);
    
29.     int isSort = 0;
    
30.     int i;
    
31.     while(!isSort) {
    
32.         shuffle(l, sizeof(l[0]), n);
    
33.         isSort = 1;
    
34.         for(i = 0; i < n-1; i++) {
    
35.             if (l[i] > l[i+1]){
    
36.                 isSort = 0;
    
37.                 break;
    
38.             }
    
39.         }
    
40.     }
    
41.     end = time(NULL);
    
42.     for(int i=0; i<9; i++){
    
43.         printf("%d ", l[i]);
    
44.     }
    
45.     printf("\n总共耗时：%ld秒\n", end - begin);
    
46. }

复制代码

1. 67 70 73 101 104 105 108 111 118
   
2. 总共耗时：0秒

复制代码

跳转到最佳答案楼层

qiuyouzhi

你真的认真读了这份代码吗？
代码里面写的很清楚了吧

傻眼貓咪

猴子排序本来就是效率极低的方法
其最坏时间复杂度：无限
平均时间复杂度：O(n*n!)

雨中漫步~

傻眼貓咪 发表于 2021-10-8 20:13
猴子排序本来就是效率极低的方法
其最坏时间复杂度：无限
平均时间复杂度：O(n*n!)

“对 9 个整数进行 10 次排序，最差的结果是 10 秒钟，最快在 1 秒钟内可以得出结果”，那示例的演示结果用时最长10秒是偶然事件？

雨中漫步~

qiuyouzhi 发表于 2021-10-8 20:13
你真的认真读了这份代码吗？
代码里面写的很清楚了吧

还请您指点

傻眼貓咪

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. 
   
5. void swap(void *a, void *b) {
   
6.     unsigned char *p = a;
   
7.     unsigned char *q = b;
   
8.     unsigned char tmp;
   
9.     tmp = *p;        
   
10.     *p = *q;         
    
11.     *q = tmp;        
    
12. }
    
13. 
    
14. void shuffle(void *x, int size_elem, int total_elem) {
    
15.     int i = total_elem - 1;            
    
16.     for(i ; i >= 0; --i) {
    
17.         int r = rand() % (i+1);
    
18.         swap(x + r*size_elem, x + i*size_elem);
    
19.     }                 
    
20. }
    
21. 
    
22. int main(int argc, char *argv[]) {
    
23.     time_t begin, end;
    
24.     begin = time(NULL);
    
25.     srand((unsigned)time(NULL));
    
26.     int l[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
    
27.     int n;
    
28.     n = sizeof(l)/sizeof(l[0]);
    
29.     int isSort = 0;
    
30.     int i;
    
31.     while(!isSort) {
    
32.         shuffle(l, sizeof(l[0]), n);
    
33.         isSort = 1;
    
34.         for(i = 0; i < n-1; i++) {
    
35.             if (l[i] > l[i+1]){
    
36.                 isSort = 0;
    
37.                 break;
    
38.             }
    
39.         }
    
40.     }
    
41.     end = time(NULL);
    
42.     for(int i=0; i<9; i++){
    
43.         printf("%d ", l[i]);
    
44.     }
    
45.     printf("\n总共耗时：%ld秒\n", end - begin);
    
46. }

复制代码

1. 67 70 73 101 104 105 108 111 118
   
2. 总共耗时：0秒

复制代码

qiuyouzhi

雨中漫步~ 发表于 2021-10-8 20:22
还请您指点

你可以去查一下这个 Bogo 排序，
它的本质是用随机数作为下标来排序，每随机完一次就检查一遍是否排好序了。
所以它的排序时间就是靠运气的。

雨中漫步~

qiuyouzhi 发表于 2021-10-8 21:10
你可以去查一下这个 Bogo 排序，
它的本质是用随机数作为下标来排序，每随机完一次就检查一遍是否排好序 ...

谢谢

雨中漫步~

傻眼貓咪 发表于 2021-10-8 20:40

您这个程序思路上和参考程序一致，为什么运行结果更快，最多一秒，而示例程序运行时间不定？

傻眼貓咪

你的代码第15行多了个冒号 ; 而且输出结果也不正确

雨中漫步~

傻眼貓咪 发表于 2021-10-9 13:36
你的代码第15行多了个冒号 ; 而且输出结果也不正确

这里的；不是多余，只是循环体为空，相当于下面这段

1. int i = 0;
   
2.                 int count = 0;
   
3.         while (array[i] <= array[i+1] && i < length -1 )
   
4.         {
   
5.                  count++;
   
6.                 }
   
7. 
   
8.         if (count == length - 1)
   
9.         {
   
10.                 return 1;
    
11.         }
    
12.         else
    
13.         {
    
14.                 return 0;
    
15.         }

复制代码

傻眼貓咪

雨中漫步~ 发表于 2021-10-9 14:54
这里的；不是多余，只是循环体为空，相当于下面这段

变成无限循环
范例：

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     while(1)
   
6.     ;
   
7.    
   
8.     printf("program is end!");
   
9.     return 0;
   
10. }

复制代码

这里永远不会打印 "program is end!"，因为上面的 while 无限循环

雨中漫步~

傻眼貓咪 发表于 2021-10-9 15:13
变成无限循环
范例：这里永远不会打印 "program is end!"，因为上面的 while 无限循环

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int i = 0;
   
6.         int l[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
   
7.        
   
8.     while(l[i] <= l[i+1] && ++i < 8)
   
9.             ;
   
10.    
    
11.     printf("program is end!");
    
12.     return 0;
    
13. }

复制代码

循环体while()里的判断语句并不是一直为真

傻眼貓咪

雨中漫步~ 发表于 2021-10-9 15:47
循环体while()里的判断语句并不是一直为真

你说的没有错，但是你的代码可能出于某些原因导致 while 一直处于 真（这是因为我尝试去掉冒号后，得出的结论），你试试检查看看。非常抱歉兄弟，我的能力不足。

雨中漫步~

傻眼貓咪 发表于 2021-10-9 16:05
你说的没有错，但是你的代码可能出于某些原因导致 while 一直处于 真（这是因为我尝试去掉冒号后，得出 ...

非常感谢你耐心的解答