912.排序数组（桶排序）

题目

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解法

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// BucketSort 桶排序int n = nums.size();// 获取数组的最小值和最大值int maxNum = nums[0], minNum = nums[0];for (int i = 1; i < n; ++i) {if (nums[i] > maxNum) maxNum = nums[i];if (nums[i] < minNum) minNum = nums[i];}// 初始化桶int bucketNum = 5, bucketSize = (maxNum - minNum) / bucketNum + 1;vector<vector<int>> buckets(bucketNum, vector<int>(0));// 小至大分桶for (int num : nums) {int bucketIndex = (num - minNum) / bucketSize;buckets[bucketIndex].emplace_back(num);}// 桶内排序for (int i = 0; i < buckets.size(); ++i) {sort(buckets[i].begin(), buckets[i].end());}// 从桶中依次取数int index = 0;for (auto& bucket : buckets) {for (int num : bucket) {nums[index++] = num;}}return nums;}
};