S1E32猴子排序问题,C\C++交流,编程语言专区,鱼C论坛

雨中漫步~ 发表于 2021-10-8 20:01:57

S1E32猴子排序问题

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int in_order(int array[], int length);
void shuffle(int array[], int length);
void bogo_sort(int array[], int length);

int in_order(int array[], int length)
{
   int i = 0;

   while (array <= array && ++i < length - 1)
            ;

   if (i == length - 1)
   {
            return 1;
   }
   else
   {
            return 0;
   }
}

void shuffle(int array[], int length)
{
   int index, temp, i;
   static int t1, t2;

   srand(t1);
   t1 = rand();

   t2 = time(NULL);
   srand(t1+t2);

   for (i = 0; i < length; i++)
   {
            index = rand() % (length - i) + i;
            if (index != i)
            {
                     temp = array;
                     array = array;
                     array = temp;
            }
   }
}

void bogo_sort(int array[], int length)
{
   while (!in_order(array, length))
   {
            shuffle(array, length);
   }
}

int main(void)
{
   int array[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
   int i, length;
   time_t begin, end;

   begin = time(NULL);

   length = sizeof(array) / sizeof(array);

bogo_sort(array, length);

   printf("排序后的结果是：");
   for (i = 0; i < length; i++)
   {
            printf("%d ", array);
   }
   putchar('\n');

   end = time(NULL);
   printf("总共耗时：%ld秒\n", end - begin);

   return 0;
}

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int in_order(int array[], int length);
void shuffle(int array[], int length);
void bogo_sort(int a[], int n);

int in_order(int array[], int length)//判断洗牌后的数组中数字是否顺序排列
{
int i = 0;

while(array < array && ++i < length -1)
;

if (i == length - 1)
{
return 1;
}
else
{
return 0;
}
}

void shuffle(int array[], int length)// 随机排序
{
int index, temp, i;

srand(time(NULL));    //rand(time(NULL)) 获得随机数的间隔是 1 秒 1 次

for (i = 0;i < length;i++)
{
index = rand() % (length - i) + i;
if (index != i)
{
temp = array;
array = array;
array = temp;
}
}
}

void bogo_sort(int array[], int length) //当与目标字符串一致时跳出循环
{
while (!in_order(array, length))
{
shuffle(array, length);
}
}

int main(void)
{
   int array[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
   int i, length;
   time_t begin, end;

   begin = time(NULL); //time：获取当前系统时间（UTC时间）的time_t值

   length = sizeof(array) / sizeof(array);
   bogo_sort(array, length);

   printf("排序后的结果是：");
   for (i = 0; i < length; i++)
   {
            printf("%d ", array);
   }
   putchar('\n');

   end = time(NULL);
   printf("总共耗时：%ld秒\n", end - begin);

   return 0;
}

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

qiuyouzhi 发表于 2021-10-8 20:13:27

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

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

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

雨中漫步~ 发表于 2021-10-8 20:21:26

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

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

雨中漫步~ 发表于 2021-10-8 20:22:04

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

还请您指点

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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(void *a, void *b) {
unsigned char *p = a;
unsigned char *q = b;
unsigned char tmp;
tmp = *p;
*p = *q;
*q = tmp;
}

void shuffle(void *x, int size_elem, int total_elem) {
int i = total_elem - 1;
for(i ; i >= 0; --i) {
   int r = rand() % (i+1);
   swap(x + r*size_elem, x + i*size_elem);
}
}

int main(int argc, char *argv[]) {
time_t begin, end;
begin = time(NULL);
srand((unsigned)time(NULL));
int l[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
int n;
n = sizeof(l)/sizeof(l);
int isSort = 0;
int i;
while(!isSort) {
   shuffle(l, sizeof(l), n);
   isSort = 1;
   for(i = 0; i < n-1; i++) {
         if (l > l){
            isSort = 0;
            break;
         }
   }
}
end = time(NULL);
for(int i=0; i<9; i++){
   printf("%d ", l);
}
printf("\n总共耗时：%ld秒\n", end - begin);
}67 70 73 101 104 105 108 111 118
总共耗时：0秒

qiuyouzhi 发表于 2021-10-8 21:10:13

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

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

雨中漫步~ 发表于 2021-10-8 21:23:08

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

谢谢

雨中漫步~ 发表于 2021-10-9 12:23:39

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

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

傻眼貓咪 发表于 2021-10-9 13:36:44

本帖最后由傻眼貓咪于 2021-10-9 13:37 编辑

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

雨中漫步~ 发表于 2021-10-9 14:54:13

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

这里的；不是多余，只是循环体为空，相当于下面这段int i = 0;
int count = 0;
   while (array <= array && i < length -1 )
   {
      count++;
}

   if (count == length - 1)
   {
            return 1;
   }
   else
   {
            return 0;
   }

傻眼貓咪 发表于 2021-10-9 15:13:52

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

变成无限循环
范例：#include <stdio.h>

int main()
{
while(1)
;

printf("program is end!");
return 0;
}这里永远不会打印 "program is end!"，因为上面的 while 无限循环

雨中漫步~ 发表于 2021-10-9 15:47:57

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

#include <stdio.h>

int main()
{
int i = 0;
int l[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

while(l <= l && ++i < 8)
;

printf("program is end!");
return 0;
}

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

傻眼貓咪 发表于 2021-10-9 16:05:13

本帖最后由傻眼貓咪于 2021-10-9 16:07 编辑

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

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

雨中漫步~ 发表于 2021-10-9 16:38:29

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

非常感谢你耐心的解答

页: [1]

鱼C论坛's Archiver

S1E32猴子排序问题