数据结构|基数排序及八个排序总结

一、基数排序

基数排序是一种非比较型整数排序算法，也称桶排序，它的基本思想是通过对数据的每一位进行排序，低位优先，从最低位到最高位依次进行进桶出桶操作，循环count次（count为最大值的位数)，最终实现整个数据序列的有序排列。

桶排序不能处理负数。

1.算法思想

算法原理

• 基数排序是基于桶排序的思想，将整数按位数切割成不同的数字，然后按每个位数分别进行排序。
• 对于每个位数，使用稳定的排序算法（如计数排序）将元素分配到不同的桶中，然后再按顺序收集桶中的元素。
• 从最低位开始，依次对每一位进行上述操作，直到最高位处理完毕，此时整个序列就有序了。

进桶：

出桶：

以此类推。 

十位：

百位：

2.代码实现

//基数排序

static int GetFigur(int* arr, int len)
{
	int max = arr[0];
	for (int i = 0; i < len; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	//求位数//丢个位
	int count = 0;
	while (max != 0)
	{
		count++;
		max /= 10;
	}
	return count;
}
//获取十进制整数右数第figur位的数，figur从0开始
static int GetNum(int n, int figur)
{
	for (int i = 0; i > figur; i++)
	{
		n /= 10;
	}
	return n % 10;
}

void RadixSort(int* arr, int len)
{
	//定义10个队列
	HNode queArr[10];
	for (int i = 0; i < 10; i++)
	{
		InitQueue(&queArr[i]);
	}

	//得到最大数字的位数，确定进队和出队的趟数
	int count = GetFigur(arr, len);

	int index;//队列的下标
	for (int i = 0; i < count; i++)
	{
		//入队
		for (int j = 0; j < len; j++)//遍历数组入队
		{
			index = GetNum(arr[j], i);//index保存arr[j]进入队列的下标
			Push(&queArr[index], arr[j]);
		}
		//依次出队
		int j = 0;//arr的下标
		for (int k = 0; k < 10; k++)
		{
			while(!IsEmpty(&queArr[k]))	
			{
				Pop(&queArr[k], &arr[j++]);
			}
		}
	}
	for (int i = 0; i < 10; i++)
	{
		Destroy(&queArr[i]);
	}
}

3.复杂度分析

时间复杂度：O(d*n) d为最大数据的位数

空间复杂度：桶排序需要额外的空间来存储桶和桶内元素，空间复杂度为O(n)。
稳定性：桶排序是稳定的排序算法。在桶排序过程中，每个桶内的元素在排序时会保持相对顺序不变。例如，对于相同大小的元素，先进入桶的元素会先被处理，从而保证了它们在排序后的相对顺序与原始序列一致。

二、八大排序总结

以上是排序算法第四部分关于基数排序的知识以及八大排序算法的总结，如果有帮助可以点赞收藏，会持续更新输出有用的内容，感兴趣可以关注我！