|
10鱼币
#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;
}
}
}
}
问题描述 写小甲鱼的那个猴子排序算法,为什么我这个代码一直得不到升序的排序结果
BOGO 随机排序是一种概率性的排序算法,
其基本思想是:随机打乱数组元素的顺序,然后检查是否已经排序。
如果没有排序,那就再次打乱顺序,如此往复,直到数组被排序。
它的时间复杂度可能是O(n!),也可能是O(∞),
这两个时间复杂度都是非常夸张的存在……
所以在有限的时间内看到它没有返回结果,是完全可能的事情!
|
最佳答案
查看完整内容
BOGO 随机排序是一种概率性的排序算法,
其基本思想是:随机打乱数组元素的顺序,然后检查是否已经排序。
如果没有排序,那就再次打乱顺序,如此往复,直到数组被排序。
它的时间复杂度可能是O(n!),也可能是O(∞),
这两个时间复杂度都是非常夸张的存在……
所以在有限的时间内看到它没有返回结果,是完全可能的事情!
|