排序算法之线性排序(时间复杂度为线性)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之线性排序(时间复杂度为线性)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3034字，纯文字阅读大概需要5分钟。

内容图文

桶排序

• 桶排序的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独用快排或者冒泡等排序算法进行排序。桶内排完序之后，再把桶里的数据按照顺序依次取出，组成的序列就是有序的了。
• 桶排序的时间复杂度是O(n)。我们分析一下，如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk)。m个桶排序的时 间复杂度就是O(m * k * logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n*log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
• 但是桶排序对要排序数据的要求非常苛刻的。首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。 其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就 不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlogn)的排序算法了。
• 桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
• 当然可以对桶内的数据再进行一次划分，划分为更小的桶。

算法实现：

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

int _tmain(int argc, _TCHAR* argv[]){
	int array_stu[50]={0};
	int array_out[100]={0};
    
    srand((int)time(NULL));//设置随机数的基准，这样保证每次的运行结果不同

    for(int i=0;i<50;i++)
    {
        array_stu[i] =(rand()%(99-1))+1;
    }

    /*把array_stu分别扔到对应的桶里面去
    里面的逻辑需要根据要求进行修改，这里是如果数值跟桶的编号一样，就把这个桶的数据增加
    */
    for(int i=0;i<50;i++)
    {
        for(int j=1;j<100;j++)
        {
            /*如果数值跟桶的编号一样，就把这个桶的数据增加*/
            if(array_stu[i] ==j)
            {
                array_out[j] ++;
            }
        }
    }
    
    /*把排序后的数据输出*/
    for(int i=0;i<100;i++)
    {
        while(array_out[i] > 0)
        {
            printf("%d\n",i);
            array_out[i]--;
        }
    }
	return 0;
}

计数排序

• 当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分为k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//计数排序
void CountSort(int *a, int len)
{
	//通过max和min计算出临时数组所需要开辟的空间大小
	int max = a[0], min = a[0];
	for (int i = 0; i < len; i++){
		if (a[i] > max)
			max = a[i];
		//if (a[i] < min)
		//	min = a[i];
	}
	//使用calloc将数组都初始化为0
//	int range = max - min + 1;
	int *b = (int *)calloc(max, sizeof(int));
	//使用临时数组记录原始数组中每个数的个数
	for (int i = 0; i < len; i++){
		//注意：这里在存储上要在原始数组数值上减去min才不会出现越界问题
		b[a[i]] += 1;
	}
	int j = 0;
	//根据统计结果，重新对元素进行回收
	for (int i = 0; i < max; i++){
		while (b[i]){
			//注意：要将i的值加上min才能还原到原始数据
			a[j++] = i ;
			b[i]--;
		}
	}
}
//打印数组
void PrintArray(int *a, int len)
{
	for (int i = 0; i < len; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[]){
	int a[] = { 3, 4, 3, 2, 1, 2, 6, 5, 4, 7 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	CountSort(a, sizeof(a) / sizeof(int));
	printf("排序后：");
	PrintArray(a, sizeof(a) / sizeof(int));
	system("pause");
	return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

hzulwy 发布了60 篇原创文章 · 获赞 0 · 访问量 840 私信 关注

内容总结

以上是互联网集市为您收集整理的排序算法之线性排序(时间复杂度为线性)全部内容，希望文章能够帮你解决排序算法之线性排序(时间复杂度为线性)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---