【数据结构】排序算法---基数排序（动图演示）

Crossoads

发布于 2024-10-22 08:25:25

950

发布于 2024-10-22 08:25:25

文章被收录于专栏：汇编语言

⚠本节要介绍的不是计数排序

1. 定义

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为k个关键字，逐一对各个关键字排序后完成对所有元素的排序。

如果是从第1关键字到第k关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first)基数排序——最高位优先法（从高位到低位）；
如果是从第k关键字到第1关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first)基数排序——最低位优先法（从低位到高位）。

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

2. 算法步骤

2.1 MSD基数排序

将待排序的元素拆分为k个关键字，先对第1关键字进行稳定排序，然后对于每组 具有相同关键字的元素 再对第2关键字进行稳定排序（递归执行）……最后对于每组 具有相同关键字的元素 再对第k关键字进行稳定排序。

一般而言，我们默认基数排序是稳定的，所以在 MSD 基数排序中，我们也仅仅考虑借助 稳定算法（通常使用计数排序）完成内层对关键字的排序。

2.2 LSD基数排序

将待排序的元素拆分为k个关键字，然后先对 所有元素 的第k关键字进行稳定排序，再对 所有元素 的第k-1关键字进行稳定排序，再对 所有元素 的第k-2关键字进行稳定排序……最后对 所有元素 的第1关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

LSD 基数排序也需要借助一种 稳定算法 完成内层对关键字的排序。同样的，通常使用计数排序来完成。

3. LSD 基数排序动图演示

4. 性质

稳定性：

如果对内层关键字的排序是稳定的，则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法。

空间复杂度：

MSD 基数排序和 LSD 基数排序的空间复杂度都为

O(k+n)

。

时间复杂度：

基数排序每一位的比较可以使用线性排序，比如桶排序或者计数排序，当然需要保证如计数排序的稳定性。每次排序时间复杂度O(n)，那么如果有k位，则时间复杂度为

O(k*n)

,如果k不大比如手机号11位，那么时间复杂度就是

O(n)

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。一般来说，如果每个关键字的值域都不大，就可以使用 [计数排序]作为内层排序，此时的复杂度为

O(kn+{\sum_{i=1}^k}wi)

，其中

为第i关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的

O(nklogn)

排序而无需使用基数排序了。

5. 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要

O(n)

的时间复杂度，而且分配之后得到新的关键字序列又需要

O(n)

的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是

O(d*2n)

，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说

n>>k

，因此额外空间需要大概n个左右。

6. 代码实现

C语言

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d\t", a[i]);
  }
}

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1;

  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i];
    }
  }

  while (m / exp > 0) {
    int bucket[BASE] = { 0 };

    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++;
    }

    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1];
    }

    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i];
    }

    for (i = 0; i < n; i++) {
      a[i] = b[i];
    }

    exp *= BASE;

#ifdef SHOWPASS
    printf("\nPASS   : ");
    print(a, n);
#endif
  }
}

int main() {
  int arr[MAX];
  int i, n;

  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;

  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("\nARRAY  : ");
  print(&arr[0], n);

  radixsort(&arr[0], n);

  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");

  return 0;
}

Python

# coding=utf-8
def radix_sort(array):
    max_num = max(array)
    place = 1
    while max_num >= 10**place:
        place += 1
    for i in range(place):
        buckets = [[] for _ in range(10)]
        for num in array:
            radix = int(num/(10**i) % 10)
            buckets[radix].append(num)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                array[j] = num
                j += 1
    return array
 
 
if __name__ == '__main__':
    array = [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]
    print(radix_sort(array))

Java

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

C++

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

Go

var (
	K int = 3 // 基数排序需要的全局变量
	RADIX int = 10
	queue [][]int
)
func radix_sort_queue_pop(qu []int) []int {
    if len(qu) == 0 {
        return qu // 如果数组为空，不做任何操作
    }
    // 删除第一个元素
    qu = qu[1:]
    return qu
}
func radix_sort_queue_push(qu []int, data int) []int {
	qu = append(qu, data)
	return qu
}
func radix_sort_get_key(value int, k int) int {
	key := 0
	for k >= 0 {
		key = value % 10
		value /= 10
		k--
	}
	return key
}
func radix_sort_distribute(arr []int, left int, right int, k int){
	// k表示是第几次分发数据
	for i:=left; i<right; i++ {
		key := radix_sort_get_key(arr[i], k)
		queue[key] = radix_sort_queue_push(queue[key], arr[i])
	}
}
func radix_sort_collect(arr []int) {
	k := 0
	for i:=0; i < RADIX; i++ {
		for len(queue[i]) != 0 {
			arr[k] = queue[i][0] // 先进先出
			k++
			queue[i] = radix_sort_queue_pop(queue[i])
		}
	}
}
func radix_sort_by_group(arr []int, left int, right int) {
	for i:=0; i<K; i++ {
		// 分发数据
		radix_sort_distribute(arr, left, right, i)
		// 回收数据
		radix_sort_collect(arr)
	}
}
func radix_sort(arr []int, sz int) {
	// 初始化队列
	queue = make([][]int, RADIX)
	left := 0
	right := sz;
	radix_sort_by_group(arr, left, right)
}