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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

#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[i] <= array[i+1] && ++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[i];
                        array[i] = array[index];
                        array[index] = 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[0]);
        
                bogo_sort(array, length);

        printf("排序后的结果是：");
        for (i = 0; i < length; i++)
        {
                printf("%d ", array[i]);
        }
        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[i] < array[i+1] && ++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[index];
                        array[index] = array[i];
                        array[i] = 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[0]);
        bogo_sort(array, length);

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

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

        return 0;
}

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

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[0]);
    int isSort = 0;
    int i;
    while(!isSort) {
        shuffle(l, sizeof(l[0]), n);
        isSort = 1;
        for(i = 0; i < n-1; i++) {
            if (l[i] > l[i+1]){
                isSort = 0;
                break;
            }
        }
    }
    end = time(NULL);
    for(int i=0; i<9; i++){
        printf("%d ", l[i]);
    }
    printf("\n总共耗时：%ld秒\n", end - begin);
}

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

跳转到最佳答案楼层

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[0]);
    int isSort = 0;
    int i;
    while(!isSort) {
        shuffle(l, sizeof(l[0]), n);
        isSort = 1;
        for(i = 0; i < n-1; i++) {
            if (l[i] > l[i+1]){
                isSort = 0;
                break;
            }
        }
    }
    end = time(NULL);
    for(int i=0; i<9; i++){
        printf("%d ", l[i]);
    }
    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[i] <= array[i+1] && 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[i] <= l[i+1] && ++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 一直处于真（这是因为我尝试去掉冒号后，得出的结论），你试试检查看看。非常抱歉兄弟，我的能力不足。

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

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

非常感谢你耐心的解答

账号		自动登录	找回密码
密码			立即注册