LeetCode-912. 排序数组【数组分治桶排序计数排序基数排序排序堆（优先队列）归并排序】

本文主要是介绍LeetCode-912. 排序数组【数组分治桶排序计数排序基数排序排序堆（优先队列）归并排序】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode-912. 排序数组【数组分治桶排序计数排序基数排序排序堆（优先队列）归并排序】

题目描述：
解题思路一：直接sort()，但是没啥意思。
解题思路二：基数排序，这里有一个问题就是，基数排序只适合于正数整数的排序。所以这里处理的操作是将数组所有元素都减去数组的最小值，得到一个全是正数的数组。
解题思路三：0

题目描述：

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

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

解题思路一：直接sort()，但是没啥意思。

class Solution:def sortArray(self, nums: List[int]) -> List[int]:nums.sort()return nums

时间复杂度：O(n logn)
空间复杂度：O(n)

解题思路二：基数排序，这里有一个问题就是，基数排序只适合于正数整数的排序。所以这里处理的操作是将数组所有元素都减去数组的最小值，得到一个全是正数的数组。

其余的操作就是正常的基数排序，就是直接分为十个桶(0-9十位刚好十个桶)。然后按照个位,十位,百位…上面对应的数放入桶中进行排序。而基数排序可以在 O(N)的时间内完成整数之间的排序。

class Solution:def sortArray(self, nums: List[int]) -> List[int]:# """基数排序"""pos = 0 # 记录当前正在排拿一位，最低位为1min_num = min(nums)  # 最小值，可能是负数# 为了避免负数，数组中所有元素减去最小值for i in range(len(nums)):nums[i] -= min_nummax_num = max(nums)  # 最大值digit = len(str(max_num))  # 记录最大值的位数while pos < digit:bucket_list =[[] for _ in range(10)] #初始化桶数组for x in nums:bucket_list[int(x / (10**pos)) % 10].append(x) # 找到位置放入桶数组nums.clear()for x in bucket_list:   # 放回原序列for y in x:nums.append(y)pos += 1# 还原数组for i in range(len(nums)):nums[i] += min_numreturn nums