php专区

 首页 > php专区 > PHP进阶 > 算法 > 利用数组的索引也可以排序

利用数组的索引也可以排序

分享到:
【字体:
导读:
         摘要:看到一道算法面试题,比较有趣,我自己用C做了一下。题目:随机生成10个100以内的整数,把数据从小到大排序,而且算法复杂度只能是1。这个算法比较有意思的地方是,首先建立一个数组B,其元素个数为数组A的最大元素值,然后用A的元素作为B的数组下标,然后给存在的B元素赋值,这样就可以用循环把下标输出出来。 ...

利用数组的索引也可以排序

看到一道算法面试题,比较有趣,我自己用C做了一下。

题目:随机生成10个100以内的整数,把数据从小到大排序,而且算法复杂度只能是1。

这个算法比较有意思的地方是,首先建立一个数组B,其元素个数为数组A的最大元素值,然后用A的元素作为B的数组下标,然后给存在的B元素赋值,这样就可以用循环把下标输出出来。

C程序如下:

#include 
#include 
#include 
#define random(x) (rand()%x)
main()
{
    int lengthA, lengthB, i;
	int wait;
    
	int arrayA[10]; // 定义一个数组
	int arrayB[101];
	srand(time(NULL)); // 让每次产生的随机数都不一样
	lengthA = sizeof(arrayA) / sizeof(arrayA[0]);
	lengthB = sizeof(arrayB) / sizeof(arrayB[0]);
		
	// 给数组赋值
	for(i = 0; i < 10; i++)
		arrayA[i] = random(100);
	printf("随机生成的数组A的元素为 n");
	// 输出数组
	for(i = 0; i < 10; i++)
		printf("%dn", arrayA[i]);
	for (i = 0; i < lengthA; i++)
    {
        arrayB[arrayA[i]] = 101;
    }
	printf("排序后的结果为n");
	for (i = 0; i < lengthB; i++)
    {
        if (arrayB[i] == 101)
            printf("%dn", i);
    }
	//printf("%d", lengthA);
	scanf("%d", &wait);
}

程序运行结果:

随机生成的数组A的元素为
79
62
87
43
32
52
72
88
44
53
排序后的结果为
32
43
44
52
53
62
72
79
87
88

本文地址:http://www.nowamagic.net/librarys/veda/detail/508,欢迎访问原出处。

利用数组的索引也可以排序
分享到:
趣味算法之兔子产子问题
趣味算法之兔子产子问题 假定你有一雄一雌一对刚出生的兔子,它们在长到一个月大小时开始交配,在第二月结束时,雌兔子产下另一对兔子,过了一个月后它们也开始繁殖,如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子,假定没有兔子死亡,在一年后总共会有多少对兔子? 在一月底,最初的一对兔子交...
如何将一个数组的元素顺序打乱
如何将一个数组的元素顺序打乱 给定一个数组,要求把数组内元素的顺序随机打乱,然后输出,主要是要保证效率。 这个算法其实简单,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。代码如下...
  •         php迷,一个php技术的分享社区,专属您自己的技术摘抄本、收藏夹。
  • 在这里……