Task 03： 数组排序
第7天打卡，附上学习链接
1 学习内容
1.1 计数排序（Counting Sort）
使用一个额外的数组counts，其中第i个元素count[i]是待排序数组arr中值等于i的元素个数，然后根据数组counts来将arr中的元素排到正确的位置。
算法步骤：
（1）找出待排序数组中最大值元素和最小值元素；
（2）统计数组中每个值为i的元素出现的次数，存在数组的第i项；
（3）对所有计数累加（从counts中的第一个元素开始，每一项和前一项累加）；
（4）反向填充目标数组：将每个元素i放在新数组的第counts[i]项，每放一个元素就要将counts[i] -= 1。
算法分析：
当输入元素是n个0~k之间的整数时，计数排序的时间复杂度为O(n+k)；
由于用于计数的数组counts的长度取决于待排序数组中数据的范围（等于待排序数组最大值减去最小值再加1），所以计数排序对于数据范围很大的数组，需要大量的时间和内存；
计数排序一般用于排序整数，不适用于按字母顺序排序人名；
计数排序时稳定排序算法。
代码实现：
def countingSort(arr):
arr_min, arr_max = min(arr), max(arr)
size = arr_max - arr_min + 1
counts = [0 for _ in range(size)]
for num in arr:
counts[num - arr_min] += 1
for j in range(1, size):
counts[j] += counts[j - 1]
res = [0 for _ in range(len(arr))]
for i in range(len(arr) - 1, -1, -1):
res[counts[arr[i] - arr_min] - 1] = arr[i]
counts[arr[i] - arr_min] -= 1
return res
1.2 桶排序（Bucket Sort）
将未排序的数组分到若干个桶中，每个桶的元素再进行单独排序。
算法步骤：
（1）将区间划分为n个相同大小的子区间，每个区间称为一个桶；
（2）遍历数组，将每个元素装入对应的桶中；
（3）对每个桶内的元素单独排序（使用插入、归并、快排等算法）；
（4）最后按照顺序将桶内的元素合并起来。
算法分析：
桶排序可以在线性时间内完成排序，当输入元素个数为n，桶的个数是m时，桶排序时间复杂度为O(m+n)；
由于桶排序使用了辅助空间，所以空间复杂度是O(n+m)；
如果桶内使用插入排序等稳定排序算法，则桶排序也是稳定排序算法。
代码实现：
def insertionSort(arr):
for i in range(1, len(arr)):
temp = arr[i]
j = i
while j > 0 and arr[j - 1] > temp:
arr[j] = arr[j - 1]
j -= 1
arr[j] = temp
return arr
def bucketSort(arr, bucket_size = 5):
arr_min, arr_max = min(arr), max(arr)
bucket_count = (arr_max - arr_min) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for num in arr:
buckets[(num - arr_min) // bucket_size].append(num)
res = []
for bucket in buckets:
insertionSort(bucket)
res.extend(bucket)
return res
1.3 基数排序（Radix Sort）
将整数按位数切割成不同的数字，然后按每个位数分别比较进行排序。
算法步骤：基数排序算法可以采用最低位优先法（Least Significant Digit First）或者最高位优先法（Most Significant Digit first），最常用的是前者。
（1）遍历数组元素，获取数组最大值元素，并取得位数；
（2）以个位元素为索引，对数组元素排序；
（3）合并数组；
（4）之后依次以十位、百位...，直到最大值元素的最高位处值为索引，进行排序，并合并数组，最终完成排序。
算法分析：
基数排序的时间复杂度是O(k*n)，其中n是待排序元素的个数，k是数字位数。k的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小；
基数排序的空间复杂度是O(n+k)；
基数排序是稳定排序算法。
代码实现：
def radixSort(arr):
size = len(str(max(arr)))
for i in range(size):
buckets = [[] for _ in range(10)]
for num in arr:
buckets[num // (10**i) % 10].append(num)
arr.clear()
for bucket in buckets:
for num in bucket:
arr.append(num)
return arr
2 练习题目
2.1 1122 数组的相对排序 *
题目描述：给出两个数组arr1和arr2，arr2中的元素各不相同，arr2中的每个元素都出现在arr1中，对arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。 样例1：输入为arr1=[2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], arr2=[2, 1, 4, 3, 9, 6]，输出为[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]。
解题思路：自定义排序。
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
def mycmp(x: int) -> (int, int):
return (0, rank[x]) if x in rank else (1, x)
rank = {x: i for i, x in enumerate(arr2)}
arr1.sort(key=mycmp)
return arr1
时间复杂度：O(mlogm+n)； 空间复杂度：O(logm+n)。
2.2 0908 最小差值I *
题目描述：一个整数数组nums，给每个元素都加上一个任意数字x(-k<=x<=k)，从而得到一个新数组result。返回数组result的最大值和最小值之间可能存在的最小差值。 样例1：输入为nums=[1]， k=0，输出0； 样例2：输入为nums=[0, 10]，k=2，输出为6； 样例3：输入为num=[1, 3, 6]，k=3，输出为0。
解题思路：求B最大与最小之间的最小差值，希望的是max(B)更小，min(B)更大。max(B)最小的极 限值是max(A)-k，min(B)最大的极限值是min(A)+k，所以最小差值至少为(max(A)-k) - (min(A)+k)。
class Solution:
def smallestRangeI(self, nums: List[int], k: int) -> int:
return max(0, max(A)-min(A) - 2*k)
时间复杂度：O(n)； 空间复杂度：O(1)。
2.3 0164 最大间距 ***
题目描述：给一个无序数组nums，要找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于2，则返回0。 样例1：输入为arr=[3, 2, 1], k=2，输出为[1, 2]或[2, 1]； 样例2：输入为arr=[0, 1, 2, 1], k=1，输出为[0]。
解题思路：基数排序，元素个数小于2的单独处理。
class Solution:
def radixSort(arr):
size = len(str(max(arr)))
for i in range(size):
buckets = [[] for _ in range(10)]
for num in arr:
buckets[num // (10**i) % 10].append(num)
arr.clear()
for bucket in buckets:
for num in bucket:
arr.append(num)
return arr
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
arr = self.radixSort(nums)
return max(arr[i] - arr[i-1] for i in range(1, len(arr)))
