2.6.桶排序

桶排序

桶排序也是一种非常快的排序算法，但是对于个别数组中某个元素比较大的情况比较费内存。它的实现分为三个步骤：

第一步，根据数组创建桶。具体桶的个数取决于数组中元素的大小，所谓桶其实也是一个数组，只不过桶的索引代表数组的元素，而索引值代表在原数组中此元素的个数，例如对于需要排序的数组{1，2，3，5}而言，需要创建一个桶，计数完成后为{0，1，1，1，0，1}

第二步，对数组进行计数，计得的数存储到桶中，也就是把元素的大小当作桶的索引，从这里就可以看出来，桶的大小取决于数组中元素的最大值，而在传参的时候也要传入一个参数为数组中元素的最大值。当然这也是可选的，也可以传入数组之后再用max_element函数计算出来，而且对于大多数需要排列的数组，多出来的这点时间复杂度不值一提。

第三步，就是根据桶进行排序了，这步就是第二步的反向操作。

#include <iostream>
#include <vector>
using namespace std;

void bucketSort(vector<int>& arr, int maxValue) {
    if (arr.empty()) return;
	//1.创建桶
    int n = arr.size();
    vector<int> bucket(maxValue + 1, 0);
	//2.计数
    for (int i = 0; i < n; i++) {
        bucket[arr[i]]++;
    }
	//3.排序
    int index = 0;
    for (int i = 0; i <= maxValue; i++) {
        while (bucket[i] > 0) {
            arr[index++] = i;
            bucket[i]--;
        }
    }
}

int main() {
    vector<int> arr = { 3, 2, 1, 4, 5, 6, 7, 8, 9, 10 };
    int maxValue = *max_element(arr.begin(), arr.end());
    bucketSort(arr, maxValue);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

时间和空间复杂度分析：

• 时间复杂度: O(n + k)，其中n为数组中元素个数，k为数组中最大元素＋1
  • 用于创建桶。
  • 用于填充桶。
  • 用于重建排序后的数组。
• 空间复杂度: O(k)
  • 主要用于存储桶向量。