本文共 2388 字，大约阅读时间需要 7 分钟。

一. 基数排序是什么？

基数排序是一种针对整数的非比较型排序算法，它通过将整数按照位数分割成独立的数字，并依据这些数字对整数进行排序。这一方法不需要进行比较，因此可以在某些情况下超越比较排序的效率限制。

基数排序的核心思想是将整数从最低位（个位）开始，逐步向高位（如十位、百位等）排序。在每一轮排序中，数字的某一位会被固定，然后在下一轮排序中处理下一高位。整个过程类似于对数字进行逐位排列，最终将数字按照从低到高的顺序排列完毕。

二. 基数排序的工作原理

为了更好地理解基数排序，我们可以通过具体例子来分析其过程。以数组 {27, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25} 为例，我们可以按照以下步骤进行基数排序：

最终，通过逐位排序，数组将被完全排序为 {1, 5, 17, 23, 25, 27, 28, 67, 72, 84, 91, 97}。

三. C++代码实现

#include 
   
    
#include 
    
     
using namespace std;
template
     
      
void print(E A[], int n) {
    for (int i = 0; i < n; ++i) {
        if (i == n - 1) {
            cout << A[i] << endl;
        } else {
            cout << A[i] << " ";
        }
    }
}
template
      
       
void radix_sort(E A[], E B[], int n, int k, int r, int cnt[]) {
    int j;
    for (int i = 0; i < k; ++i) {
        for (j = n - 1; j >= 0; --j) {
            int key = A[j] / (r * (1 + i));
            if (cnt[key] > 0) {
                B[--cnt[key]] = A[j];
            } else {
                B[n] = A[j];
            }
        }
        for (j = 0; j < n; ++j) {
            int key = A[j] / (r * (1 + i));
            B[j] = A[j];
        }
        for (i = 0; i < k; ++i) {
            for (j = n - 1; j >= 0; --j) {
                key = A[j] / (r * (1 + i));
                if (cnt[key]) {
                    B[--cnt[key]] = A[j];
                } else {
                    B[n] = A[j];
                }
            }
        }
    }
}
int main() {
    vector
       
         arr = {27, 91, 1, 97, 17, 23, 84, 28, 72, 5, 67, 25};
    vector
        
          sorted_arr(arr.size(), 0); int cnt[20] = {0}; radix_sort(arr, sorted_arr, arr.size(), 3, 10, cnt); print(sorted_arr, arr.size()); return 0; }
        
       
      
     
    
   

代码解释

通过以上内容，读者可以清楚地了解基数排序的原理及其在 C++ 中的实现方式。