【题解】《算法零基础100讲》(第40讲) 非比较排序 - 基数排序

一. 基数排序

??基数排序(radix sort)：属于分配式排序，又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog?m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

如图：

分析：

1. 首先是根据各位数字的大小进行装桶，或说分配，到对应的下标0~9。
2. 然后再从0开始按顺序取出。
3. 再然后按照十位上的数字进行分配。
4. 以此类推。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int GetDigit(int M, int i) //取整数M的第i位数
{
    while (i > 1){
    M /= 10;i--;}return M % 10;
}void radix_sort(int num[], int len)
{
    int i, j, k, l, digit;int allot[10][10];	//《分配数组》memset(allot, 0, sizeof(allot));//初始化《分配数组》for (i = 1; i <= 10; i++){
    //分配相应位数的数据，并存入《分配数组》for (j = 0; j < len; j++){
    digit = GetDigit(num[j], i);k = 0;while (allot[digit][k])k++;allot[digit][k] = num[j];}//将《分配数组》的数据依次收集到原数组中l = 0;for (j = 0; j < 10; j++){
    k = 0;while (allot[j][k] > 0){
    num[l++] = allot[j][k];k++;}}//每次分配，收集后初始化《分配数组》，用于下一位数的分配和收集memset(allot, 0, sizeof(allot));}
}int main(){
    int arr[] = {
     10, 43, 59, 29, 65, 79, 54, 90, 68 };int arrSize = sizeof(arr) / sizeof(arr[0]);radix_sort(arr, arrSize);for (int i = 0; i < arrSize; i++){
    printf("%d ", arr[i]);}putchar('\n');return 0;
}

二. 推荐专栏

??

《算法零基础100讲》(第40讲) 非比较排序 - 基数排序

??
??

三. 相关练习

3.1 最大间距

题目链接：

164. 最大间距

我们可以用上面的基数排序模板对其进行排序，然后找出最大差值，也可以用C语言提供的函数qsort进行排序。

代码如下：

int cmp(int *a, int *b){
    return *b < *a;}
int maximumGap(int* nums, int numsSize){
    qsort(nums ,numsSize ,sizeof(int) ,cmp);//排序int max = 0;	//默认为0for(int i = 1;i < numsSize;i++)//从1开始遍历if(max < nums[i] - nums[i - 1]) max = nums[i] - nums[i - 1];return max;
}