基数排序(桶排序)——C语言实现

这篇具有很好参考价值的文章主要介绍了基数排序(桶排序)——C语言实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  本期我们讲解基数排序,基数排序讲完后,我们的常用排序算法专栏就已经讲完了,后续可能会出一些排序优化问题,以及排序算法结合C语言实战,比如迷宫求解🅿停车场系统机房预约系统以及植物大战僵尸外挂等等小项目。本人从零开始学习云计算的专栏也在不断更新中,喜欢的小伙伴可以继续关注。

基数排序c语言,常用排序算法,c语言,排序算法,算法

基数排序c语言,常用排序算法,c语言,排序算法,算法

🥒一、基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或binsort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,在某些时候,基数排序法的效率高于其它的稳定性排序法。

🍉二、排序思想

💉基数排序就是桶排序,也可以说是桶排序的一种,基数排序固定式九个桶,分别对应的是0~9十个数字。基数排序的基本思想是:先将待排序序列按个位数排好,然后按顺序复制回原数组;再按十位排序好,再按顺序复制回原数组;依次类推,按百位、千位,排序的趟数就是最大数的位数,比如千位数就要排四趟,百位数就要排3趟

🥭三、动图演示

  我们先来看看基数排序的动图演示,一定要格外注意,把桶里面的数组放回去时,有些桶只有一个数,有些桶有多个数,而这些多个数的桶,他的数据放回去时,是按照放下来的顺序放回去的,也就是先下来的先上去这点很重要,🙉🙉后面要考。

基数排序c语言,常用排序算法,c语言,排序算法,算法

🍍四、图解

  看了上面的动图,是不是感觉基数排序的思想及其简单,但是代码却是极为不好写,很复杂。因为我们得弄清楚,桶里面到底装的是什么,是数据本身吗?如果不是,数据本身存放在哪里?让我们接着往下看👇👇👇👇
基数排序c语言,常用排序算法,c语言,排序算法,算法
  接下来讲解一下上图是什么意思。因为我们是按数据的每一位进行排序,所以我们就得定义九个桶,根据数据的位值,将待排序的序列按位值丢进桶里面(但不是真的丢进去),上图中我们已经将数据按照各位丢进了各自的桶中,这时候我们只需要按顺序将这些数据再次放回原数组就可以了,但是,怎么放?这个顺序怎么找,很明显,我们得借助一个临时数组,这个临时数组和原数组等长,用来先存放这些要归还的数据。现在我们就需要将这些数从后往前放到临时数组(为什么要从后往前后面会剖析),到底要怎么放?👀👀拿上面的例子举例,我们可以提前知道,最后放进临时数组的顺序是这样的
基数排序c语言,常用排序算法,c语言,排序算法,算法
  我们从49开始放,现在我们只需要知道49的下标是几,就能够把数据精准的放进去,那么49的下标6是怎么来的呢?很简单,因为49的前面有六个数啊,哈哈哈,是不是很简单?那么,这六个数的6怎么得来?🌝🌝🌝🌝

🥕🥕答案就是:先统计每个桶里面有多少个数,这是真正要放在桶里面的数据,然后前后累加,每个桶里面的元素就代表着累计加起来总共有多少个数。将这个数减去1就可以得到每个数该放到临时数组的下标。

🍓五、代码实现(包含详细注释)

//基数排序
void RadixSort(int* arr, int n)
{
	//max为数组中最大值
	int max = arr[0];
	int base = 1;

	//找出数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	//循环结束max就是数组最大值


	//临时存放数组元素的空间
	int* tmp = (int*)malloc(sizeof(int)*n);

	//循环次数为最大数的位数
	while (max / base > 0)
	{
		//定义十个桶,桶里面装的不是数据本身,而是每一轮排序对应(十、白、千...)位的个数
		//统计每个桶里面装几个数
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++)
		{
			//arr[i] / base % 10可以取到个位、十位、百位对应的数字
			bucket[arr[i] / base % 10]++;
		}
		//循环结束就已经统计好了本轮每个桶里面应该装几个数


		//将桶里面的元素依次累加起来,就可以知道元素存放在临时数组中的位置
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}
		//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置


		//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}
		//不能从前往后放,因为这样会导致十位排好了个位又乱了,百位排好了十位又乱了
		/*for (int i = 0; i < n; i++)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}*/

		//把临时数组里面的数拷贝回去
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmp[i];
		}
		base *= 10;
	}
	free(tmp);
}

🍒六、问题解答

  我们解答一下前面一直强调的问题,将数据放到临时数组时为什么要从后往前放。我们来看看,
基数排序c语言,常用排序算法,c语言,排序算法,算法
🌲🌲对于这个数组,我们按各位排完的顺序应该是如上图所示,对于四号桶,先排的34,后排的1234,因为34先被拿下来,但如果我们从前往后排,就会导致1234在前,34在后,因为我们代码是这样写的,i先扫到的元素会放到后面一个位置,bucket[arr[i] / base % 10]再减减,减减之后就是前一个位置了。意思就是,我们早就已经为四号桶准备了两个位置放置元素,谁先放,就会被放到下标大的那个位置。所以我们从后往前放,就能将本应该放到下标大的位置的1234放到它正确的位置上

	//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}

🍇七、致命缺陷(负数问题)

  我们当前的程序只能排正数,一旦出现负数,程序就崩了。我们如何解决呢?

  🌈💨答案就是:既然出现了负数,我们只需要将所有的数加上一个数,把所有的数变为非负数即可。那么这个数是什么呢?没错,就是数组里面最小数的绝对值,加上这个数后,排完序再将这个数给它减掉即可。

优化后的代码为

//基数排序
void RadixSort(int* arr, int n)
{
	//max为数组中最大最小值
	int max = arr[0];
	int min = arr[0];
	int base = 1;

	//找出数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//循环结束max就是数组最大最小值

	//循环将数组的元素全部变为正数
	//所有元素加上最小值的绝对值
	for (int i = 0; i < n; i++)
	{
		arr[i] += abs(min);
	}

	//临时存放数组元素的空间
	int* tmp = (int*)malloc(sizeof(int)*n);

	//循环次数为最大数的位数
	while (max / base > 0)
	{
		//定义十个桶,桶里面装的不是数据本身,而是每一轮排序对应(十、白、千...)位的个数
		//统计每个桶里面装几个数
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++)
		{
			//arr[i] / base % 10可以取到个位、十位、百位对应的数字
			bucket[arr[i] / base % 10]++;
		}
		//循环结束就已经统计好了本轮每个桶里面应该装几个数


		//将桶里面的元素依次累加起来,就可以知道元素存放在临时数组中的位置
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}
		//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置


		//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}
		//不能从前往后放,因为这样会导致十位排好了个位又乱了,百位排好了十位又乱了
		/*for (int i = 0; i < n; i++)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}*/

		//把临时数组里面的数拷贝回去
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmp[i];
		}
		base *= 10;
	}
	free(tmp);

	//还原原数组
	for (int i = 0; i < n; i++)
	{
		arr[i] -= abs(min);
	}
}

         👆回到顶部👆

基数排序c语言,常用排序算法,c语言,排序算法,算法文章来源地址https://www.toymoban.com/news/detail-776227.html

到了这里,关于基数排序(桶排序)——C语言实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 排序算法————基数排序(RadixSort)

    什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(K+M ) 基数排序是一种借助多的思想对单逻辑进行排序的方法。 基数排序根据每个位来分配

    2024年02月13日
    浏览(34)
  • 十大排序算法(下):计数排序,基数排序,桶排序

    有n个数,取值范围是 0~n,写出一个排序算法,要求时间复杂度和空间复杂度都是O(n)的 我们知道,前面介绍的基于比较的排序算法中,最好的算法,其平均时间复杂度都在O(N),达到线性的时间复杂度就要使用新的排序算法,而这种方法,就称为是计数排序。 计数排序的思路

    2024年02月05日
    浏览(38)
  • 深入浅出排序算法之基数排序

    目录 1. 前言 1.1 什么是基数排序⭐⭐⭐ 1.2 执行流程⭐⭐⭐⭐⭐ 2. 代码实现⭐⭐⭐ 3. 性能分析⭐⭐ 3.1 时间复杂度 3.2 空间复杂度 一个算法,只有理解算法的思路才是真正地认识该算法,不能单纯记住某个算法的实现代码! (1) 通过键值得各个位的值,将要排序的元素分配

    2024年02月08日
    浏览(56)
  • 【算法】排序算法(插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、基数排序、堆排序)

    插入排序 :插入排序、希尔排序 选择排序 :选择排序、堆排序 交换排序 :冒泡排序、快速排序 归并排序 基数排序(又叫桶排序) (1)思路图解 从头开始比较相邻元素的值(就是从下标较小的元素开始),使值较大的元素逐渐从前移向后部,就像水里的气泡一样,越来越大,向上

    2024年03月25日
    浏览(54)
  • 【数据结构与算法】基数排序

    基数排序 基数排序(Radix Sort)属于“分配式排序”,又称“桶子法”或 bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。 基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法。 基数排序是桶排序。 基

    2024年02月15日
    浏览(41)
  • 用C语言对学生成绩进行排序(归并排序与基数排序)

    我们内部排序已经学了插入排序(直接插入排序、折半插入排序、希尔排序),交换排序(冒泡排序、快速排序),选择排序(简单选择排序、堆排序),这些都属于内部排序,接下来我们学习内部排序里面剩下的归并排序和基数排序。 归并排序与上述基于交换、选择等排序

    2024年02月16日
    浏览(36)
  • 数据结构与算法Python版:基数排序

    简介 :基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中

    2024年01月24日
    浏览(42)
  • (java版)排序算法----【冒泡,选择,插入,希尔,快速排序,归并排序,基数排序,堆排序】超详细~~

    目录 冒泡排序(BubbleSort): 代码详解:  冒泡排序的优化:  选择排序(SelectSort): 代码详解:  插入排序(InsertSort): 代码详解:  希尔排序(ShellSort):  法一(交换法)代码详解:  法二(移位法--插入排序的优化)代码详解: 快速排序(QuickSort):  代码详解:  归并排

    2024年02月20日
    浏览(48)
  • 【Python排序算法】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

    目录 1 冒泡排序(Bubble Sort) 2 插入排序(Insertion Sort) 3 选择排序(Selection Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6 堆排序 (Heap Sort) 7 计数排序 (Counting Sort) 8 基数排序 (Radix Sort) 9 希尔排序(Shell Sort) 10 桶排序     1 冒泡排序(Bubble Sort)        冒泡排序

    2024年02月08日
    浏览(55)
  • 十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

    目录 一、冒泡排序: 二、插入排序: 三、选择排序: 四、希尔排序: 五、堆排序: 六、快速排序: 6.1挖坑法: 6.2左右指针法 6.3前后指针法: 七、归并排序: 八、桶排序: 九、计数排序: 9.1绝对映射: 9.2现对映射: 十、基数排序:  1、思路: 通过对待排序序列从前

    2024年03月11日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包