计数排序与桶排序区别

计数排序和桶排序是两种不同的排序算法，但它们有一些相似之处。以下是对它们的详细解释：

计数排序 (Counting Sort)

计数排序是一种非比较排序算法，适用于对一定范围内的整数排序。其基本思想是利用数组下标作为值来记录每个数出现的次数，然后通过这些计数值直接构建有序的输出数组。

计数排序步骤：

1. 找出待排序数组中的最大值和最小值，计算范围大小。
2. 创建一个计数数组，记录每个值出现的次数。
3. 对计数数组进行累加，确定每个元素在排序后数组中的位置。
4. 根据计数数组中的信息，将待排序数组中的元素放置到正确的位置，构建有序数组。

示例代码：

#include <iostream>
#include <vector>

void countingSort(int arr[], int n) {
    int max_val = *std::max_element(arr, arr + n);
    int min_val = *std::min_element(arr, arr + n);
    int range = max_val - min_val + 1;

    std::vector<int> count(range, 0), output(n);

    // 统计每个值出现的次数
    for (int i = 0; i < n; i++)
        count[arr[i] - min_val]++;

    // 修改计数数组，累加前面的计数值
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // 构建有序数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }

    // 将结果拷贝回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);

    std::cout << "Sorted array is: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    return 0;
}

桶排序 (Bucket Sort)

桶排序是一种分布式排序算法，通常用于对浮点数排序。其基本思想是将数据分到几个有序的桶中，然后对每个桶内的数据进行排序，最后合并各个桶中的数据得到有序的结果。

桶排序步骤：

1. 创建若干个桶，将数据分配到不同的桶中。
2. 对每个桶内部进行排序（通常使用插入排序）。
3. 合并所有桶中的数据，得到排序后的结果。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

void bucketSort(float arr[], int n) {
    std::vector<float> buckets[n];

    // 将数据分配到桶中
    for (int i = 0; i < n; i++) {
        int bucket_index = n * arr[i];
        buckets[bucket_index].push_back(arr[i]);
    }

    // 对每个桶内部进行排序
    for (int i = 0; i < n; i++)
        std::sort(buckets[i].begin(), buckets[i].end());

    // 合并所有桶中的数据
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);

    std::cout << "Sorted array is: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";
    return 0;
}

区别与联系

• 范围与适用场景：

  • 计数排序适用于范围较小的整数排序。
  • 桶排序适用于均匀分布的浮点数排序。

• 时间复杂度：

  • 计数排序的时间复杂度为 (O(n + k))，其中 (n) 是数组大小，(k) 是数值范围。
  • 桶排序的时间复杂度为 (O(n + k))，但依赖于桶内排序算法。

• 空间复杂度：

  • 计数排序的空间复杂度为 (O(k))。
  • 桶排序的空间复杂度为 (O(n + k))。

总之，计数排序和桶排序虽然有一些相似之处，但它们适用于不同的场景和数据类型，各有优缺点【5†source】【6†source】。