友情提示:本文共有 1067 个字,阅读大概需要 3 分钟。
前言
今天和大家分享一个排序方法,以我们空间换取时间的问题,在很多程序员面试的时候很容易被问到我们排序算法的问题,在被问到种类问题的时候我们需要很清楚地知道排序的对象,然后采取最好的排序方法,而不是所有的排序你都只用一种排序算法,虽然也可以排序出来但是对于不同的排序对象,选择合适的拍讯算法可能提高我们的排序效率。
那么今天我们来讲什么呢,我们讲一个对于比较集中的数字排序,什么叫集中这,举一个例子,在一定范围内的,比如考试分数0分到100分之间,或者年龄大多在0到100之间等类似这样你知道范围并且范围相对集中的排序我觉得今天讲的这种方法无疑是最适合的,关键是这种办法不不需要数和数之间进行比较大小的,我们邀请来看一下我们的算法原理。
算法时间复杂度
这是什么意思呢,我们在学算法的时候都会学到空间复杂度和时间复杂度,一般来说我们时间越短占用的地址月小那么这个算法就是好算法,我们看一下面几种比较有代表性的时间复杂度。
T(n)= O(1)
T(n)= O(n)
T(n)= O(n2)
我们可以看到随着排序数量的增加我们算法的时间复杂度就可以体现我们一个算法的优劣。
以地址换取时间
我们回到今天的主题,我们怎么选择一种针对一组范围相对集中的数据进行排序呢,我说过了最好的办法就是以地址换取时间,我们开辟出一块内存空间用来存放要排序的数据,这样我们不用比较大小也可以很快得把数据排序出来,我们举一个例子,给一组范围0到~20之内的数字排序;
(1)我们知道范围是0到20,那么我们就向内存申请一个大小为20的数组array[20],并把数组内所有元素都初始化为0,用来统计数据,
(2)我们开始遍历没有排序的数组,规则是:我们遍历到的数字作为array数组的下标,然后对应下标加1,比如:我们遍历到数字5,那么array[5]的值加1,如果遍历数字是13,那么array[13]的值加1,这样把需要排序的数字都遍历完一遍。
(3)排序最后一步就是打印我们array数组中值不为0的下标,因为我们初始化的时候所有元素值都为0,经过第二步的赋值,有一些元素会被改变,被改变的值的下标就是我们要排序的数字,这时候 我们只要遍历array数组把元素不为0的下标打印出来那么打印出来的就是我们排序的结果。
代码实现
#include
#include
#include
int main ()
{
int array[20]={0};
int a[13]={1,7,1,8,2,4,3,16,10,11,19,12,0};
printf("排序前数组n");
for(int i=0;i<13;i++)
{
printf("%-5d",a[i]);
int c=a[i];
array[c]+=1;
}
printf("n");
printf("排序后数组n");
for(int i=0;i<20;i++)
{
if(array[i] == 0)
continue;
else
{
for(int j=0;j printf("%-5d",i); } } printf("n"); return 0; } 代码结果 我们可以看出来排序的效果的没有出现错误的,然后值得注意的是如果我们我们数组中有相同的数字我们一定要记得处理一下,代码中我在遍历的时候如果值为0那么我就跳过,如果值不为0那么就打印,打印的时候又循环一遍,如果值是2那么就是说下标数据出现了两次那么我们也应该要打印两次。这样就解决了相同数据的排序问题。 其他用途 其实严格来说这种并不是一种排序算法,更多用在统计方面,比如果你要统计一篇文章中某个字母出现的个数,在设置密码的时候安全性该一点的都会要求需要字母和数字搭配使用,这时候你也可以用此类办法判断设置的密码是不是满足要求了,判断一个号码中每一个数字出现的次数等等,这些都可以用该方法来统计。算法是死的,但是我们是活的所以使用的时候可以不要局限于某一个方向。 最后结束了,感谢你的阅读,如果你有不太懂的地方可以在评论区说出来,大家一起探讨和学习哦! 本文如果对你有帮助,请点赞收藏《C语言面试题:不比较数据大小对数据进行排序》,同时在此感谢原作者。