1778 字
9 分钟

极致排序算法

2026-01-20
算法
算法
/
排序
/
基数排序
/
C++

极致排序算法#

桶排序#

典型的空间换时间算法，天然具有O(n)的时间复杂度，但对于数据较为离散的时候容易出现空间浪费

  • 数据必须为无符号整数，且具有上限#
  • 比较冒泡排序，快排等基于比较排序的上线O(n log n)的时间复杂度更低#
  • 空间复杂度为O(n * k)#
  • 当数据较为离散，空间浪费较为严重#
  • 当数据上线过高，需要的空间极大#

C++代码实现

#include <vector>


#define NUMMAX 10000// 数据上限
#define length 100  // 数据长度


void bin_sort(uint32_t *list,size_t n){
    vector<uint32_t> bin(NUMMAX);
    for (size_t i = 0; i < n; i++) {
        uint32_t x = a[i];
        bin[x]++;
    }
    size_t index = 0;
    for (size_t i = 0; i < bin.size(); i++) {
        for(size_t j = 0;j < bin[i];j++){
            a[index++] = i;
        }
    }
}

桶排序的稳定性#

排序算法的稳定性是排序过程中，对于数值相同的两个元素的位置是否会出现改变

即假定有这么一串数据

[
    {"name":"小明","score":99},
    {"name":"小东","score":27},
    {"name":"小西","score":63},
    {"name":"小红","score":70},
    {"name":"小白","score":70}
]

在经过排序算法的排序后，成绩相同的小红和小白的前后是否一致，当排序后小红仍然在小白前面恒成立，即可以称算法稳定，反之即为不稳定。

// 上述案例是将name作为判断key
// 可以修改 DataType 的类型自定义结构体做验证
// 并将以下代码作为桶排序优化的开始
#define DataType uint32_t
void radix_sort(DataType *a,size_t n)
{
  // 桶排序
  // 声明一个二维数组，10000个桶
  vector<vector<DataType>> bin(NUMMAX);
  for (size_t i = 0; i < n; i++) {
    DataType x = a[i];
    bin[x].push_back(x);
  }


  // 将桶中的元素放回原数组
  size_t index = 0;
  for (size_t i = 0; i < bin.size(); i++) {
    if (bin[i].empty()) continue;
    for (auto x : bin[i]) {
      a[index++] = x;
    }
  }
}

利用稳定性，我们可以将桶排序进行拆分优化，将比较的数字拆做一个个十以内的数字组合

例如: [12,321,2,12,32,4323,12,2]

单独看个位数做排序，进行排序后: [321, 12, 2, 12, 32, 12, 2, 4323]

第二次看十位排序，当十位不存在时，其结果为0: [2, 2, 12, 12, 12, 321, 4323, 32]

以此类推，会逐渐排序完成。因为其稳定所以在单独看某位数时排序也不会乱

# Python实现，比较容易复现
arr = [12,321,2,12,32,4323,12,2]


def radix_sort(arr):
    bin  = [[] for _ in range(10)]
    for i in range(len(arr)):
        x = arr[i]
        bin[x // 1 % 10].append(x)
    arr = []
    for i in bin:
        for j in i:
            arr.append(j)
    print(arr)


radix_sort(arr)

C++实现

void radix_sort(uint32_t *a,size_t n)
{
  vector<vector<uint32_t>> bin(10);
  // 处理个位数的排序
  for (size_t i = 0; i < n; i++) {
    uint32_t x = a[i];
    bin[x % 10].push_back(x);
  }
  // 将桶中的元素放回原数组
  size_t index = 0;
  for (size_t i = 0; i < 10; i++) {
    if (bin[i].empty()) continue;
    for (auto x : bin[i]) {
      a[index++] = x;
    }
  }
    // 清空容器
  for (size_t i = 0; i < 10; i++) {
    bin[i].clear();
  }


  // 处理十位数
  for (size_t i = 0; i < n; i++) {
    uint32_t x = a[i];
    bin[x / 10 % 10].push_back(x);
  }
    // 以此类推......
}

上述例子中，我们采用10进行数据分段方便理解，计算机中的基础还是二进制，采用二进制可以使计算中除法运算换成位运算，会更加便捷高效，以10000为例

> 10000 % 256
16
> bin(10000)
0b10011100010000
> bin(256)
0b11111111
# 10011100010000
# 00000011111111
# 做 与(and) 操作
# 00000000010000 = 16
> 10000 // 256
39
> 10000 & 8
39
# 256 = 2的8次方
# 注意看，第一行的前8位置移到后面，变成第二行
# 0010 0111 0001 0000 = 10000 >> 8
# 0000 0000 0010 0111 = 39

C++代码实现

void radix_sort(uint32_t *a,size_t n)
{
  vector<vector<uint32_t>> bin(0x100);


  for (size_t p = 0; p < 4; p++) {
    // 清空桶
    for (size_t i = 0; i < bin.size(); i++) {
      bin[i].clear();
    }
    // 计算偏移量
    uint16_t shift = p * 8;
    // 将元素放入桶中
    for (size_t i = 0; i < n; i++) {
      uint32_t x = a[i];
      bin[(x >> shift) & 0xff].push_back(x);
    }
    // 将桶中的元素放回原数组
    size_t index = 0;
    for (size_t i = 0; i < bin.size(); i++) {
      if (bin[i].empty()) continue;
      for (auto x : bin[i]) {
        a[index++] = x;
      }
    }
  }
}

同时我们可以发现，实现中出现了大量容器的push_back操作，尽管我们在算法中常常将函数调用视作为常数时间计算，但是容器的频繁扩容也会带来大量IO操作。虽然我们无法预测每个桶的大小，但是我们可以通过预先统计桶的大小，根据大小分配容器大小，就可以避免数组的获取和释放了。

void radix_sort(uint32_t *a,size_t n)
{
  vector<vector<uint32_t>> bin(0x100);
  vector<size_t> count(0x100); // 统计每个桶的元素数量
  vector<size_t> offset(0x100); // 统计每个桶的当前数据量
  for (size_t p = 0; p < 4; p++) {
    size_t i = 0, shift = p * 8;
    for (i = 0; i < bin.size(); i++) {
      bin[i].clear();
      offset[i] = 0;
      count[i] = 0;
    }
    for (i = 0; i < n; i++) // 原本的push_back操作改为先统计数量
      count[(a[i] >> shift) & 0xff]++;
    for (i = 0; i < bin.size(); i++) // 预分配空间
      bin[i].resize(count[i]);


    for (i = 0; i < n; i++) { // 放入对应的桶中
      uint32_t index = (a[i] >> shift) & 0xff;
      bin[index][offset[index]++] = a[i];
    }


    size_t index = 0;
    for (i = 0; i < bin.size(); i++) {
      if (bin[i].empty()) continue;
      for (auto x : bin[i]) {
        a[index++] = x;
      }
    }
  }
}

前缀和#

既然我们已经可以知道每个桶的大小，那我们也可以通过扁平化二位数组实现数组访问速度的优化

void radix_sort(uint32_t *a,size_t n)
{
  vector<uint32_t> bin(n); // 扁平化数组
  vector<size_t> count(0x100); // 统计每个桶的元素数量
  vector<size_t> offset(0x100); // 每个桶的当前位置
  for (size_t p = 0; p < 4; p++) {
    size_t i = 0, shift = p * 8;
    for (i = 0; i < 256; i++) {
      offset[i] = 0;
      count[i] = 0;
    }
    for (i = 0; i < n; i++) // 原本的push_back操作改为先统计数量
      count[(a[i] >> shift) & 0xff]++;
    size_t sum = 0;
    for (i = 0; i < 256; i++)
      offset[i] = sum,  // 计算每个桶的起始位置
      sum += count[i];  // 前缀和
    for (i = 0;i < n; i++) { // 放入对应的桶中
      uint32_t index = (a[i] >> shift) & 0xff;
      bin[offset[index]++] = a[i];
    }


    for (size_t i = 0; i < bin.size(); i++) {
      a[i] = bin[i];
    }
  }
}

double buffer 双缓冲#

从之前优化的代码可以看出，我们在每次排序过后，都需要将数据从bin拷贝的a，这其实不必要的。我们可以利用双缓冲，调换排序的指针做一个小优化

void radix_sort(uint32_t *a,size_t n)
{
  vector<uint32_t> bin(n);    // 扁平化排序数组
  vector<size_t> count(0x100);  // 统计每个桶的元素数量
  vector<size_t> offset(0x100); // 统计每个桶的当前数据量


  uint32_t* b = bin.data();    // 当前操作的数组指针


  for (size_t p = 0; p < 4; p++) {
    size_t i = 0, shift = p * 8;
    for (i = 0; i < 256; i++) {
      offset[i] = 0;
      count[i] = 0;
    }
    for (i = 0; i < n; i++) // 原本的push_back操作改为先统计数量
      count[(a[i] >> shift) & 0xff]++;
    size_t sum = 0;
    for (i = 0; i < 256; i++)
      offset[i] = sum,  // 计算每个桶的起始位置
      sum += count[i];
    for (i = 0;i < n; i++) { // 放入对应的桶中
      uint32_t index = (a[i] >> shift) & 0xff;
      b[offset[index]++] = a[i];
    }
    swap(a, b); // 交换指针，下一轮继续处理
  }
}

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

极致排序算法
https://firefly.cuteleaf.cn/posts/radix_sort/
作者
Lireal
发布于
2026-01-20
许可协议
CC BY-NC-SA 4.0
Lireal 后端项目创建
Python日志模块
© 2026 Lireal. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Firefly

目录