基数排序入门介绍和实现方法

分类：知识百科 日期： 点击：0

基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，按每个位数分别比较。它是一种稳定的排序算法，时间复杂度为O(n * k)，其中n是要排序的数字个数，k是数字的最大位数。

基数排序实现方法

基数排序的实现方法可以分为以下几个步骤：

  • 取得数组中的最大数，并取得位数；
  • arr为原始数组，从最低位开始取每个位组成radix数组；
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
  • 将排序好的radix数组拷贝到arr数组中；
  • 当最高位排序完成后，将arr数组拷贝到original数组中，以此类推，直到一位排序完成。

示例代码

// 基数排序，arr是数组，n是数组长度，maxDigit是数组中最大数的位数
void radixSort(int* arr, int n, int maxDigit)
{
  int i, j;
  int radix = 1; // 代表位数对应的数：1,10,100...
  int* tmp = (int*)malloc(n*sizeof(int));
  // 计数排序
  for(i = 1; i <= maxDigit; i++) {
    int count[10] = {0}; // 存放各个桶的数据统计个数
    // 统计每个桶中的记录数
    for(j = 0; j < n; j++) {
      int subKey = (arr[j] / radix) % 10;
      count[subKey]++;
    }
    // count[i]表示第i个桶的右边界索引
    for(j = 1; j < 10; j++) {
      count[j] = count[j - 1] + count[j];
    }
    // 将数据依次装入桶中
    // 这里要从右向左扫描，保证排序稳定性
    for(j = n - 1; j >= 0; j--) {
      int subKey = (arr[j] / radix) % 10;
      tmp[--count[subKey]] = arr[j];
    }
    // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
    for(j = 0; j < n; j++) {
      arr[j] = tmp[j];
    }
    radix = radix * 10;
  }
  free(tmp);
}

基数排序是一种非比较型整数排序算法，它是一种稳定的排序算法，时间复杂度为O(n * k)，其实现方法可以分为取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序；将排序好的radix数组拷贝到arr数组中；当最高位排序完成后，将arr数组拷贝到original数组中，以此类推，直到一位排序完成。

标签：