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

比较有意思的一个排序算法
服务器君一共花费了247.806 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

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

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

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

C程序如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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("%d\n", 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("%d\n", 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,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/508

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《致加西亚的信》 阿尔伯特·哈伯德(Hubbard.E.) (作者), 赵立光 (译者), 艾柯 (译者)

《致加西亚的信(经典盒装版)》内容简介:美西战争爆发以后,美国必须立即与古巴起义军首领加西亚取得联系,并获得他的合作。但当时,加西亚身在古巴的深山里——没有人知道他的确切地点,所以没法与他取得联系。这时,有人向总统推荐一个名叫罗文的人,说他有办法找到加西亚,而且也只有他才能找得到。他们找来罗文,交给他一封写给加西亚的信。三周后,罗文徒步走过一个危机四伏的国家,最终把那封信交给了加西亚。 此后,罗文的事迹被传为佳话,“送信”成为了敬业、忠诚、勤奋的象征,罗文便成了每个领导都想找到的人和每个员工都应该学习和效仿的榜样。

更多计算机宝库...