【手撕排序算法】---基数排序

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

个人主页:平行线也会相交
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创
收录于专栏【数据结构初阶(C实现)】
【手撕排序算法】---基数排序,数据结构初阶(C实现),排序算法,算法

我们直到一般的排序都是通过关键字的比较和移动这两种操作来进行排序的。
而今天介绍的基数排序并不是依靠关键字的比较和移动来进行数据元素的排序。
基数排序是一种借助多关键字的思想对单逻辑关键字进行排序方法。

1️⃣样例演示

基数排序的概念描述和思想比较难懂,所以我们先来一个样例演示。然后再来细细品味基数排序的概念和思想。

我们对下面这个数组中的元素进行排序来进行演示:

int arr[10] = { 177 208 64 910 586 182 405 239 83 1 }

我们按照最低位优先法发来进行排序,可以看到数组中最高位为百位,所以总共要进行三轮排序

第一趟:
【手撕排序算法】---基数排序,数据结构初阶(C实现),排序算法,算法
第二趟:
【手撕排序算法】---基数排序,数据结构初阶(C实现),排序算法,算法
第三趟:
【手撕排序算法】---基数排序,数据结构初阶(C实现),排序算法,算法
可以看到每趟排序后回收数据时按照队列先进先出的思想来进行回收数据

2️⃣基数排序介绍

基数排序(Radix Sort)是一种非比较排序算法,它将待排序的元素按照位数从低位到高位(从高位到低位也可以)依次进行排序。(本文按照从低位到高位为例进行演示)。

3️⃣算法思想

基数排序的算法思想可以概括为以下几个步骤:

1.确定待排序元素的最高位数(即最大位数):首先需要确定待排序元素中的最大值,并计算出它的位数,这决定了排序过程需要进行多少轮。
2.按照最低有效位进行一次稳定的排序:从最低位开始,将待排序元素按照最低有效位的值进行稳定排序,可以使用计数排序或桶排序等算法实现。排序后,元素相对于最低位来说是有序的。
3.按照次低有效位进行稳定排序:将上一轮排序得到的有序序列按照次低有效位的值进行稳定排序。这样,在当前位和低位均已有序的前提下,排序后整个序列相对于当前位来说是有序的。
4.重复执行步骤3,直到按照最高位进行排序:依次对每一位进行稳定排序,直到按照最高位排序完成。最终得到的序列即为完全有序的结果。

4️⃣代码示例

#include<iostream>
#include<queue>
using namespace std;

#define RADIX 10
#define K 3          //排序3轮

queue<int> Q[RADIX];

int getkey(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}

void distribute(int arr[], int left, int right,int k)
{
	for (int i = left; i < right; i++)
	{
		int key = getkey(arr[i], k);
		Q[key].push(arr[i]);
	}
}

void collect(int arr[])
{
	int k = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!Q[i].empty())
		{
			arr[k++] = Q[i].front();
			Q[i].pop();
		}
	}
}
void ridixsort(int arr[], int left, int right)
{
	for (int i = 0; i < K; i++)
	{
		//分发数据
		distribute(arr, left, right, i);


		//回收数据
		collect(arr);
	}
	
}

int main()
{
	int arr[] = { 177 ,208 ,64, 910 ,586, 182, 405, 239, 83, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	ridixsort(arr, 0, n);

	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

运行结果如下:
【手撕排序算法】---基数排序,数据结构初阶(C实现),排序算法,算法

5️⃣总结

关于基数排序的几大要点总结一下:

1.基数排序是一种非比较排序算法,通过将待排序的元素按照位数进行拆分,并依次对每一位进行稳定的排序,从而达到整体有序的效果。
2.基数排序的稳定性非常重要,即在每一轮排序时,保证相同位上值相等的元素的相对顺序不变。
3.确定待排序元素的最高位数,这决定了排序过程需要进行多少轮。
4.对每一位依次进行稳定排序,可以使用计数排序、桶排序等方法来实现。
5.基数排序的时间复杂度为O(dn),其中d为待排序元素的最大位数,n为元素的个数。空间复杂度为O(n + k),其中k为计数排序或桶排序中桶的个数。
6.基数排序适用于待排序元素位数相对较小且范围较小的情况,但如果待排序元素的位数差异较大,或者位数较多时,性能可能受到影响。
7.基数排序是稳定的排序算法,可以应用于对整数、字符串等类型的数据进行排序。文章来源地址https://www.toymoban.com/news/detail-597145.html

到了这里,关于【手撕排序算法】---基数排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构与算法篇】手撕排序算法之插入排序与希尔排序

    ​👻内容专栏:《数据结构与算法篇》 🐨本文概括: 讲述排序的概念、直接插入排序、希尔排序、插入排序和希尔排序的区别。 🐼本文作者:花 碟 🐸发布时间:2023.6.13 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的

    2024年02月09日
    浏览(52)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(50)
  • 【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想: 假设现在已经有一个有序序列,如果有一个数字插入到这段序列的末尾,我们会选择拿这个数和它前面的每个数字都比较一遍,如果前面的数字比他大,那我们就让前面的数字赋值到这个被插入的数字位置,依次与前面的数

    2024年02月01日
    浏览(117)
  • 【手撕排序算法】---基数排序

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 我们直到一般的排序都是通过的 比较和移动 这两种操作来进行排序的。 而今天介绍的基数排序并不是依靠的 比较和移动 来

    2024年02月16日
    浏览(34)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏: 《数据结构与算法篇》 🐨本文概括: 利用数据结构栈(Stack)来模拟递归,实现快排的非递归版本;递归版本测试OJ题时,有大量重复元素样例不能通过,导致性能下降,优化快速排序通过将数组划分为三个区域,可以更有效地处理重复元素。 🐼本文作者:

    2024年02月11日
    浏览(83)
  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(47)
  • 数据结构:排序干货!(7大排序汇总+快速排序的优化+计数排序+基数排序+桶排序)

    目录 概念 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 双向选择排序 堆排序 交换排序 冒泡排序 快速排序 Hoare法 挖坑法 前后指针法 快排的优化 三数取中法 非递归快排 归并排序 分治算法+二路归并 非递归归并 应用 排序总结 其他排序 计数排序 简单版本 复杂

    2024年02月06日
    浏览(46)
  • [数据结构 -- 手撕排序算法第六篇] 递归实现快速排序(集霍尔版本,挖坑法,前后指针法为一篇的实现方法,很能打)

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、快速排序的实现方法 2.1 基本思想 3 hoare(霍尔)版本 3.1 实现思路 3.2 思路图解 3.3 为什么实现思路的步骤2、3不能交换 3.4 hoare版本代码实现 3.5 hoare版本代码测试 4、挖坑法 4.1 实现思路 4.2 思路图解 4.3 挖坑法代码实现 4.4 挖坑

    2024年02月16日
    浏览(49)
  • 【数据结构】手撕排序

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 排序 :所谓排序就是使一串记录,按照其中的某个或某些的大小, 递增或递减 的排列起来的操作。排序算法,就是如何使得记录按照要求

    2024年02月05日
    浏览(52)
  • [数据结构 -- 手撕排序第三篇] 冒泡排序

    目录 1、常见的排序算法 1.1 交换排序基本思想 2、冒泡排序的实现 2.1 基本思想 2.2 单趟排序 2.2.1 单趟排序分析 2.2.2 单趟排序实现代码 3、冒泡排序完整代码实现 3.1 思路分析 3.2 代码实现 4、时间复杂度 5、优化算法 5.1 优化算法思路 5.2 优化算法代码实现 6、冒泡排序的特性总

    2024年02月13日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包