排序算法11 - 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序有两种方法：

  1. LSD（Least significant digital）最低位优先，先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列。

  2. MSD（Most significant digital）最高位优先，先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。

基数排序即是计数排序的改进，也是桶排序的扩展，所以基数排序可以用桶排序法实现，也可以使用计数排序法实现。

LSD 基数排序（桶排序法）

  动图演示

  实现方法参考桶排序 -> 传送门

LSD 基数排序（计数排序法）难点

  1. 如何取元素每一位的值

    如：123 公式：个位 3 = 123 / 1 % 10 ， 十位 2 = 123 / 10 % 10 ， 百位 1 = 123 / 100 % 10 。

  2. 如何通过计数实现元素排序 如图

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  基数排序：根据键值的每位数字来分配桶；

  计数排序：每个桶只存储单一键值；

  桶排序：每个桶存储一定范围的数值

计数法代码

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

#define ARR_LEN 10 // 数组长度
#define BASE 10 // 基数（数位的取值范围为[0,9]）

void RadixSort(int arr[], int n) 
{
	int i, temp[ARR_LEN], max = arr[0], exp = 1;
	
	// 找出最大值
	for (i=1; i<n; i++) 
	{
		if (arr[i]>max) 
		{
			max = arr[i];
		}
	}

	// 从个位开始对元素的每位进行排序，最多循环到最大元素的位数，高位位数不够的元素用0进行排序
	while ( max/exp > 0 ) 
	{
		int count[BASE] = { 0 };
		
		// 各个数字出现的次数计数
		for (i=0; i<n; i++) 
		{
			count[ arr[i]/exp%BASE ]++;
		}
		
		// 计数变形，用来确定元素的排序位置
		for (i=1; i<BASE; i++) 
		{
			count[i] += count[i-1];
		}

		// 从后往前遍历元素，将其放在有序数组中的合适位置
		for (i=n-1; i>=0; i--) 
		{
			temp[ --count[arr[i]/exp%BASE] ] = arr[i];		
		}

		// 将有序数组赋值给原数组
		for (i=0; i<n; i++) 
		{
			arr[i] = temp[i];
		}

		exp *= BASE;
	}
}

int main(void)
{ 
    int i;
    int a[ARR_LEN] = {15, 24, 52, 10, 73, 19, 31, 27, 44, 48}; 
 
    RadixSort(a, ARR_LEN);
 
    printf("排序后的结果是：");
    for(i=0; i<ARR_LEN; i++)
    {
        printf("%d", a[i]);
        if(i!=ARR_LEN-1)
        {
            printf(",");
        }
    }
    printf("\n");
    return 0;
}