C++ 计数排序可视化演示

C++ 代码示例 (稳定版, 处理非负整数)

#include <vector>       // 用于 std::vector
#include <iostream>    // 用于 std::cout, std::cerr, std::endl
#include <algorithm>   // 用于 std::max_element
#include <stdexcept>   // 用于 std::out_of_range (可选的异常处理)

// 使用 std 命名空间，避免重复写 std::
using namespace std;

/**
 * @brief 使用计数排序对非负整数向量进行稳定排序。
 *
 * @param arr 待排序的整数向量 (会被原地修改)。函数假设所有元素都是非负的。
 *            如果包含负数，此实现将可能出错或行为未定义。
 */
void countingSort(vector<int>& arr) {
    // 0. 处理边界情况：空数组或只有一个元素
    if (arr.size() <= 1) {
        // cout << "数组为空或只有一个元素，无需排序。" << endl;
        return; // 直接返回
    }

    // 1. 确定范围：找到数组中的最大值 (k)
    // 使用 *max_element 找到指向最大元素的迭代器，然后解引用得到最大值
    int maxVal = 0; // 初始化为 0，防止空数组或全 0 数组出错
    bool firstElement = true;
    for (int x : arr) {
        if (x < 0) {
            cerr << "错误：计数排序当前实现不支持负数。发现值: " << x << endl;
            // 可以选择抛出异常或提前返回
            // throw std::invalid_argument("计数排序不支持负数");
            return; // 或者直接返回，不进行排序
        }
        if (firstElement) {
            maxVal = x;
            firstElement = false;
        } else if (x > maxVal) {
            maxVal = x;
        }
    }
     // 如果数组非空，现在 maxVal 是真正的最大值
     // 或者使用: if (!arr.empty()) maxVal = *max_element(arr.begin(), arr.end()); else return;


    // 2. 初始化计数数组 C
    // 大小为 k+1 (即 maxVal+1)，覆盖从 0 到 maxVal 的所有值
    // count[i] 将存储元素 i 出现的次数
    vector<int> count(maxVal + 1, 0); // 使用 vector 并初始化为 0

    // 3. 统计频率
    // 遍历输入数组 arr，统计每个元素出现的次数
    for (int x : arr) {
        // x 已经检查过是非负数且 x <= maxVal
        count[x]++; // 对应元素的计数加 1
    }

    // 4. 计算累加和 (前缀和)
    // 修改计数数组，使 count[i] 存储小于或等于 i 的元素的总个数
    // 从索引 1 开始累加
    for (int i = 1; i <= maxVal; ++i) {
        count[i] += count[i - 1];
    }
    // 现在 count[i] 表示值 i 的元素应该放在输出数组的最后一个位置的索引 + 1

    // 5. 创建临时输出数组 B
    // 大小与输入数组 arr 相同
    vector<int> output(arr.size());

    // 6. 放置元素 (反向遍历以保证稳定性)
    // 从输入数组的最后一个元素开始遍历
    for (int i = arr.size() - 1; i >= 0; --i) {
        int value = arr[i]; // 当前元素的值

        // 计算元素 value 在输出数组中的目标位置 (0-based index)
        // count[value] 是 <= value 的元素个数 (即最后一个 value 的位置 + 1)
        // 所以目标索引是 count[value] - 1
        int position = count[value] - 1;

        // 放置前检查位置有效性 (虽然理论上应该有效，增加健壮性)
        if (position < 0 || position >= output.size()) {
             cerr << "错误: 计算出的放置位置无效 (" << position << ") for value " << value << endl;
             // 可能需要错误处理或跳过
             continue; // 跳过这个元素
        }

        // 将元素放置到输出数组的计算出的位置
        output[position] = value;

        // 将 count[value] 减 1，为下一个具有相同值的元素准备前一个位置
        count[value]--;
    }

    // 7. 复制结果
    // 将排好序的输出数组 B 复制回原数组 arr
    arr = output; // 使用 vector 的赋值操作符，简洁高效
    // 或者使用 std::copy: copy(output.begin(), output.end(), arr.begin());
}

// --- 示例用法 ---
int main() {
    // 创建一个示例向量 (只包含非负整数)
    vector<int> data = {4, 2, 2, 8, 3, 3, 1, 0, 9, 5}; // 包含 0 和重复元素

    cout << "原始数组: ";
    for(int x : data) {
        cout << x << " ";
    }
    cout << endl;

    // 调用计数排序函数
    countingSort(data);

    cout << "排序后数组: ";
    for(int x : data) {
        cout << x << " ";
    }
    cout << endl << endl;

    // 测试空数组
    vector<int> emptyData = {};
    cout << "测试空数组..." << endl;
    countingSort(emptyData); // 应能安全处理
    cout << "排序后空数组: (应为空)" << endl;
    for(int x : emptyData) cout << x << " "; cout << endl << endl;


     // 测试只包含一个元素的数组
     vector<int> singleData = {5};
     cout << "测试单元素数组..." << endl;
     countingSort(singleData);
     cout << "排序后单元素数组: ";
     for(int x : singleData) cout << x << " ";
     cout << endl;

    return 0;
}

伪代码 (非负整数版)

COUNTING-SORT(A, k)  // A 是输入数组 (元素范围 0 到 k, 均为非负)
  let C[0..k] be a new array initialized to 0       // 计数数组 C
  let B[0..length[A]-1] be a new array for output // 输出数组 B

  // 步骤 1: 统计频率 (C[i] = A 中等于 i 的元素个数)
  for j = 0 to length[A] - 1
    C[A[j]] = C[A[j]] + 1

  // 步骤 2: 计算累加和 (C[i] = A 中小于或等于 i 的元素个数)
  for i = 1 to k
    C[i] = C[i] + C[i-1]

  // 步骤 3: 放置元素到输出数组 B (反向遍历保证稳定性)
  for j = length[A] - 1 downto 0
    value = A[j]                  // 获取当前元素值
    position = C[value] - 1       // 计算其在 B 中的 0-based 索引位置
    B[position] = value           // 将元素放入 B
    C[value] = C[value] - 1       // 更新 C[value]，为下一个相同元素准备位置

  // 步骤 4: (可选) 将排序后的 B 复制回 A
  // for j = 0 to length[A] - 1
  //   A[j] = B[j]

  return B // 返回排序后的数组