【C++】十大排序算法之桶排序基数排序

本次介绍内容参考自：十大经典排序算法（C++实现） - fengMisaka - 博客园 (cnblogs.com)

排序算法是《数据结构与算法》中最基本的算法之一。

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。

【十大经典排序算法分类】

【十大经典排序算法的复杂度分析】

名词解释：

时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
n：待排序列的个数。
k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。
Out-place：非原地算法，占用额外内存。
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

一、桶排序（Bucket-Sort）

桶排序（Bucket sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

1.1、算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

1.2、动图演示

桶排序动图演示

1.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file BucketSort.hpp
* @brief 桶排序
* @autor 写代码的小恐龙er
* @date 2024/03/07
*/

// 【分治法】
// 时间复杂度O(n + k)
// 空间复杂度O(n + k)



void BucketSort(int arr[], int n, int r) {
    if (arr == NULL || r < 1) return;

    // 根据最大/最小元素和桶数量，计算出每个桶对应的元素范围
    int max = arr[0], min = arr[0];
    int i, j;
    for (i = 1; i < n; i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    // 防止数据溢出 将桶个数加1[如： max - min + 1 = 10;  r = 3; 则需要四个桶]
    int range = (max - min + 1) / r++;

    // 建立桶对应的二维数组，一个桶里最多可能出现 n 个元素
    vector<vector<int>> buckets(r, vector<int>(n, 0));
    vector<int> counts(n, 0);

    for (i = 0; i < n; i++) {
        int k = (arr[i] - min) / range;
        buckets[k][counts[k]++] = arr[i];
    }

    int index = 0;
    for (i = 0; i < r; i++) {
        // 分别对每个非空桶内数据进行排序，比如计数排序
        if (counts[i] == 0) continue;
        sort(buckets[i].begin(), buckets[i].begin() + counts[i]);
        //counting_sort(buckets[i], counts[i]);
        // 拼接非空的桶内数据，得到最终的结果
        for (j = 0; j < counts[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

1.4 、算法分析

桶排序是稳定排序，但仅限于桶排序本身，假如桶内排序采用了快速排序之类的非稳定排序，那么就是不稳定的。

二、基数排序（Radix Sort）

基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

2.1 、算法描述

取得数组中的最大数，并取得位数；
arr 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）。

2.2 、动图演示

基数排序动图演示

2.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file RadixSort.hpp
* @brief 基数排序
* @autor 写代码的小恐龙er
* @date 2024/03/07
*/

// 【分治法】
// 时间复杂度O(n * k)
// 空间复杂度O(n + k)

// 基数，范围0~9
#define RADIX 10

void RadixSort(int arr[], int n) {
    // 获取最大值和最小值
    int max = arr[0], min = arr[0];
    int i, j, l;
    for (i = 1; i < n; i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    // 假如序列中有负数，所有数加上一个常数，使序列中所有值变成正数
    if (min < 0) {
        for (i = 0; i < n; i++) arr[i] -= min;
        max -= min;
    }
    // 获取最大值位数
    int d = 0;
    while (max > 0) {
        max /= RADIX;
        d ++;
    }
    vector<vector<int>> queue(RADIX, vector<int>(n, 0);

    int count[RADIX] = {0};
    for (i = 0; i < d; i++) {
        // 分配数据
        for (j = 0; j < n; j++) {
            // 依次从个位到最高位取出数值
            int key = arr[j] % (int)pow(RADIX, i + 1) / (int)pow(RADIX, i);
            // 放置到对应位数的数组中， 同时 count[key]++ 是为了 记录 位数相同的值 的个数
            queue[key][count[key]++] = arr[j];
        }
        // 收集数据
        int c = 0;
        // 依次将各个基数数组中的值排列起来 
        for (j = 0; j < RADIX; j++) {
            for (l = 0; l < count[j]; l++) {
                arr[c++] = queue[j][l];
                queue[j][l] = 0;
            }
            count[j] = 0;
        }
    }
    // 假如序列中有负数，收集排序结果时再减去前面加上的常数
    if (min < 0) {
        for (i = 0; i < n; i++) arr[i] += min;
    }
}