[已解决]写小甲鱼的那个猴子排序算法，为什么我这个代码一直得不到升序的排序结果

silver-crow

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

void bogo_sort(int array[], int 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]);
        //printf("length = %d\n", length);
        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;
}


void bogo_sort(int array[], int length)
{
    int i, j, judge = 1, t = 0;
    int random_number_set[length], mid_set[length];
    static int t1, t2;

    srand(t1);
    t1 = rand();

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

    while(judge == 1)
    {
        for(i = 0; i < length; i++)
        {
            random_number_set[i] = rand()%length;
            for(j = 0; j < i; j++)
            {
                if(random_number_set[i] == random_number_set[j])
                {
                    i--;
                    break;
                }
            }
        }

        for(i = 0; i < length; i++)
        {
            mid_set[i] = array[random_number_set[i]];
        }

        printf("新排序结果为：");
        for(i = 0; i < length; i++)
        {
            array[i] = mid_set[i];
            printf("%d ", array[i]);
            if(i == length - 1)
            {
                printf("\n");
            }
        }
   
        for(i = 0; i < length - 1; i++)
        {
            if(array[i] > array[i + 1])
            {
                break;
            }

            if(i == length - 2)
            {
                judge = 0;
            }
        }
    }   
}

问题描述 写小甲鱼的那个猴子排序算法，为什么我这个代码一直得不到升序的排序结果

最佳答案

月排行榜 / 总排行榜

小甲鱼

2023-9-14 14:11:39

BOGO 随机排序是一种概率性的排序算法，

其基本思想是：随机打乱数组元素的顺序，然后检查是否已经排序。

如果没有排序，那就再次打乱顺序，如此往复，直到数组被排序。

它的时间复杂度可能是O(n!)，也可能是O(∞)，

这两个时间复杂度都是非常夸张的存在……

所以在有限的时间内看到它没有返回结果，是完全可能的事情！

跳转到最佳答案楼层

小甲鱼

BOGO 随机排序是一种概率性的排序算法，

其基本思想是：随机打乱数组元素的顺序，然后检查是否已经排序。

如果没有排序，那就再次打乱顺序，如此往复，直到数组被排序。

它的时间复杂度可能是O(n!)，也可能是O(∞)，

这两个时间复杂度都是非常夸张的存在……

所以在有限的时间内看到它没有返回结果，是完全可能的事情！

isdkz

这个代码实现的是猴子排序算法，也就是每次随机交换数组中的元素，直到得到有序的数组。但是，由于随机交换的过程是随机的，因此可能需要很长时间才能得到有序的数组。所以，这个算法的时间复杂度是无法确定的，可能是O(n!)，也可能是O(∞)。

在这个代码中，问题可能出在随机数生成的过程中。代码中使用了srand()函数来设置随机数的种子，但是每次调用srand()函数时使用的种子都是相同的，因此生成的随机数序列也是相同的。这就导致了每次运行程序时得到的结果都是相同的，而不是随机的。

为了解决这个问题，可以使用time()函数获取当前时间，然后将其作为srand()函数的种子，这样可以保证每次运行程序时得到的随机数序列都是不同的。修改代码如下：

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

另外，由于猴子排序算法的时间复杂度非常高，因此不建议在实际应用中使用。如果需要对数组进行排序，可以使用更高效的排序算法，比如快速排序、归并排序等。

silver-crow

isdkz 发表于 2023-9-14 14:11
这个代码实现的是猴子排序算法，也就是每次随机交换数组中的元素，直到得到有序的数组。但是，由于随机交换 ...

谢谢您的回复
是这样的，您给出的解决方案，我的代码42-43行中也是这么设置的，但是一直保持循环，无法得出最后的结果

silver-crow

小甲鱼 发表于 2023-9-14 14:11
BOGO 随机排序是一种概率性的排序算法，

其基本思想是：随机打乱数组元素的顺序，然后检查是否已经排序 ...

谢谢您！！！

qbd

真是厉害