本文主要是介绍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 * 104
-5 * 104 <= nums[i] <= 5 * 104
解题思路一：直接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
时间复杂度：O(n*k)
空间复杂度：O(n+k)
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
解题思路三：0
这篇关于LeetCode-912. 排序数组【数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
