题目
示例 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 <= 50000
-50000 <= nums[i] <= 50000
常用概念
1. 大 O 复杂度：并不具体表示代码真正的复杂度，而是表示随着数据规模增长的变化趋势
2. 时间复杂度：代码执行时间或执行指令次数，通过大O复杂度表示，称为渐进时间复杂度，简称时间复杂度，一般有4种分类来表示：
2.1. 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
2.2. 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
2.3. 平均情况时间复杂度：对各类情况加权平均后的时间复杂度，或叫加权平均时间复杂度或者期望时间复杂度
2.4. 均摊时间复杂度：一种特殊的平均时间复杂度，大意是指平摊到每种执行花费的查询时间
3. 空间复杂度：类别时间复杂度的概念，表示算法的存储空间与数据规模之间的增长关系。
4. 稳定性：对于存在相等元素的待排序元素，经过排序之后，相等元素之间原始顺序是否改变
5. 原地排序：指空间复杂度是 O(1)
解法一（冒泡[n^2^]类）
思路：以冒泡为代表的一类排序算法，通过两层循环进行数据对比和排序，这类排序算法的时间复杂度为O(n^2^)，常见的排序算法包括：冒泡排序、选择排序、插入排序，3个的核心思想近似。
1. 冒泡排序：查询就像是水里的泡泡往水面冒一样，每次对比相邻两个元素，如果不满足大小关系要求就让它俩互换位置
2. 插入排序：取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入
3. 选择排序：在未排序区间的数据中，查找最小的元素，放到已排序区间的末尾
时间复杂度：O(n^2^)
空间复杂度：O(1)
稳定性：稳定（冒泡、插入），不稳定（选择）
原地排序：是
解法二、三全部算法通过了全部测试用例，解法一时间复杂度过高，数据量大的时候会超时，有个超时的测试用例有5万个正负整数，具体看链接：(https://www.zhenxiangsimple.com/files/tech/testCase20200331.txt)
冒泡排序
“`python# author：suoxd123@126.comclass Solution:#冒泡排序 def sortArray(self, nums: List[int]) -> List[int]: numLen = len(nums) for i in range(0,numLen): flag = True #提前退出冒泡循环的标志位 for j in range(0,numLen-1-i): if nums[j] > nums[j 1]: #比较相邻元素，顺序不满足时，交换位置 nums[j],nums[j 1] = nums[j 1],nums[j] flag = False #存在数据交换 if flag: break return nums“`
插入排序
“`python# author：suoxd123@126.comclass Solution:#插入排序 def sortArray(self, nums: List[int]) -> List[int]: numLen = len(nums) for i in range(1,numLen): j, tmpVal = i-1, nums[i] while j >= 0:#查找插入位置 if nums[j] > tmpVal: nums[j 1] = nums[j] # 数据向后移动 else: break #找到插入位置 j -= 1 nums[j 1] = tmpVal return nums“`
选择排序
“`python# author：suoxd123@126.comclass Solution: #选择排序 def sortArray(self, nums: List[int]) -> List[int]: numLen = len(nums) for i in range(0,numLen): minIdx, tmpVal = i, nums[i] for j in range(i 1, numLen): #查找最小值 if nums[j] < tmpVal: minIdx, tmpVal = j, nums[j] # 找到更小值 if i != minIdx: #交换最小值和无序的第一个（有序的末尾） nums[i], nums[minIdx] = nums[minIdx], nums[i] return nums“`
解法二（快排[nlogn]类）
思路：以快速排序为代表的一类排序算法，通过分治的思想实现排序，这类排序算法的时间复杂度为O(nlogn)，适合大规模的数据排序，比上面的那三种排序算法更常用，常见的排序算法包括：快速排序、归并排序，2个的核心思想基本近似。
1. 快速排序：随机选择一个数A，将小于A的放左边，大于A的数放右边，然后再分别对左右两边进行快排
2. 归并排序：将待排序元素按下标分为两部分，分别对两边递归归并排序后，再合并为一个整体
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：归并稳定，快排不稳定
原地：归并不是，快排是
快速排序
“`python# author：suoxd123@126.comclass Solution: # 将数组按分为大小两部分，并递归进行快排 def splitArray(self, nums, start, end): if start >= end: #起止中间没有数据 return splitIdx = self.getQuickIdx(nums,start, end) self.splitArray(nums, start, splitIdx-1) # 左边 self.splitArray(nums, splitIdx 1, end) # 右边 # 获取分割数值对应的索引 def getQuickIdx(self, nums, start, end): tmpVal = nums[end] #以最后一个作为分割数（也可以选第一个或其它） i = start # i 标记分割数要插入的位置（即i始终指向比tmpVal大的第一个数） for j in range(start,end 1):#也可以从左到右找大值，从右到左找小值，然后交换 if nums[j] < tmpVal: nums[i], nums[j] = nums[j], nums[i] i = 1 nums[i], nums[end] = nums[end], nums[i] return i def sortArray(self, nums: List[int]) -> List[int]: numLen = len(nums) self.splitArray(nums,0,numLen-1) return nums“`
归并排序
“`python# author：suoxd123@126.comclass Solution: # 将数组按下标递归分开为两部分 def splitArray(self, nums, start, end): if start >= end: #起止中间没有数据 return mid = int((start end) / 2) self.splitArray(nums, start, mid) # 左边 self.splitArray(nums, mid 1, end) # 右边 self.joinArray(nums, start, mid, mid 1, end) # 将两个有序数组，合并为一个有序数组 def joinArray(self, nums, leftStart, leftEnd, rightStart, rightEnd): leftIdx, rightIdx , idx, cnt= leftStart, rightStart, 0, rightEnd – leftStart 1 tmpArray = [0] * cnt # 使用两个指针分别指向两部分的最小值 while leftIdx <= leftEnd and rightIdx <= rightEnd: if nums[leftIdx] < nums[rightIdx]: tmpArray[idx] = nums[leftIdx] leftIdx = 1 else: tmpArray[idx] = nums[rightIdx] rightIdx = 1 idx = 1 #判断哪部分仍有剩余数组 tmpStart, tmpEnd = leftIdx, leftEnd if rightIdx <= rightEnd: tmpStart, tmpEnd = rightIdx, rightEnd while tmpStart <= tmpEnd: tmpArray[idx] = nums[tmpStart] idx , tmpStart = idx 1, tmpStart 1 # 将临时有序数据 放回原始数组 for i in range(0,cnt): nums[leftStart i] = tmpArray[i] def sortArray(self, nums: List[int]) -> List[int]: numLen = len(nums) self.splitArray(nums,0,numLen-1) return nums“`
解法三（桶[n]类）
思路：前面两类排序算法都是基于比较实现排序，当前以桶排序为代表的一类排序算法，都不涉及元素之间的比较，这类排序算法的时间复杂度为O(n)，适合用在有特殊属性的数据的排序，常见的排序算法包括：桶排序、计数排序、基数排序，3个的核心思想近似。
1. 桶排序：将要排序的数据分到几个有序的桶里，对每个桶里的数据进行单独排序，桶内排序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
2. 计数排序：当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，就可以把数据划分成 k 个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。
3. 基数排序：将待排序元素按位数切割成不同的数字，然后按每个位数分别比较进行排序，要求比较的排序使用稳定的排序算法。
时间复杂度：O(n)
空间复杂度：O(n)
稳定性：稳定
原地：不是
桶排序
计数排序可以当作桶排序的一种特例，对桶内的数据进行排序即为桶排序，桶内数据的排序可以使用快排或归并排序，甚至可以继续使用桶排序进行递归，本算法使用了python内置的排序。
当前桶数量选择了可以覆盖所有数值的数量，也可以选择其它数量，只要能够将数据按顺序映射到各个桶内即可。
“`python# author：suoxd123@126.comclass Solution: def sortArray(self, nums: List[int]) -> List[int]: numLen, numMin, numMax = len(nums), min(nums), max(nums) bucketCnt = numMax – numMin 1 #桶的数量可以覆盖所有数值 buckets = [[] for _ in range(0, bucketCnt)] #构建桶 for num in nums: buckets[num – numMin].append(num) for i in range(0, bucketCnt):# 桶内排序 buckets[i].sort() return [valArray[i] for valArray in buckets for i in range(0,len(valArray))]“`
计数排序
“`python# author：suoxd123@126.comclass Solution: def sortArray(self, nums: List[int]) -> List[int]: numLen, numMin, numMax = len(nums), min(nums), max(nums) tmpBucket = [0] * (numMax-numMin 1) # 申请k个桶 # 对元素进行计数（放入桶中） for num in nums: tmpBucket[num-numMin] = 1 for i in range(1,numMax-numMin 1):#把计数进行累加 tmpBucket[i] = tmpBucket[i-1] tmpArray = [0] * numLen for i in range(0,numLen):#直接将数据放入累计数量对应的索引 tmpArray[tmpBucket[nums[i]-numMin] – 1] = nums[i] tmpBucket[nums[i]-numMin] -= 1 nums = tmpArray return nums“`
基数排序
“`python# author：suoxd123@126.comclass Solution: def sortArray(self, nums: List[int]) -> List[int]: numLen, numMin = len(nums), min(nums) nums = [num – numMin for num in nums] #兼容负值 numMax = max(nums) i, j = 0, len(str(numMax)) #记录最高位数 while i < j: #从低到高，对所有位数进行排序 tmpBitArray = [[] for _ in range(10)] for num in nums: tmpBitArray[int(num / (10**i)) % 10].append(num) nums.clear()# 清除原数组 for bitArray in tmpBitArray: for val in bitArray: nums.append(val)#使用有序子序列恢复原数据 i = 1 return [num numMin for num in nums]“`
