@[toc]
排序
一、排序算法
1.1 冒泡排序
1.1.1 算法步骤
冒泡排序（Bubble Sort）基本思想：通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面。这个过程就像水底的气泡一样向上冒，这也是冒泡排序法名字的由来。
动画演示：
1.1.2 算法分析
- 时间复杂度：$O(n)$到$O(n^2)$
- 冒泡排序适用情况：冒泡排序方法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，冒泡排序方法比较适合于参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况。
- 排序稳定性：由于元素交换是在相邻元素之间进行的，不会改变值相同元素的相对位置，因此，冒泡排序法是一种 稳定排序算法。
1.1.3 代码实现：
class Solution: |
1.1.4 冒泡排序优化
优化1： 某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。
def bubble_sort2(nums): |
优化2： 记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。
def bubble_sort3(nums): |
1.2 选择排序
选择排序（Selection Sort）基本思想：每一趟排序中，从未排序部分中选出一个值最小的元素，与未排序部分第 1 个元素交换位置，从而将该元素划分到已排序部分。
1.2.1 算法步骤
- 第
1趟排序：- 无已排序部分，把第
1~n个元素（总共n个元素）作为未排序部分。 - 遍历
n个元素，使用变量min_i记录n个元素中值最小的元素位置。 - 将
min_i与未排序部分第1个元素（也就是序列的第1个元素）交换位置。如果未排序部分第1个元素就是值最小的元素位置，则不用交换。 - 此时第
1个元素为已排序部分，剩余第2~n个元素（总共n - 1个元素）为未排序部分。
- 无已排序部分，把第
- 第
2趟排序：- 遍历剩余
n - 1个元素，使用变量min_i记录n - 1个元素中值最小的元素位置。 - 将
min_i与未排序部分第1个元素（也就是序列的第2个元素）交换位置。如果未排序部分第1个元素就是值最小的元素位置，则不用交换。 - 此时第
1~2个元素为已排序部分，剩余第3~n个元素（总共n - 2个元素）为未排序部分。
- 遍历剩余
- 依次类推，对剩余
n - 2个元素重复上述排序过程，直到所有元素都变为已排序部分，则排序结束。
动画演示
1.2.2 算法分析
- 时间复杂度：$O(n^2)$。
排序法所进行的元素之间的比较次数与序列的原始状态无关，时间复杂度总是 $O(n^2)$。这是因为无论序列中元素的初始排列状态如何，第 i 趟排序要找出值最小元素都需要进行 n − i 次元素之间的比较。因此，整个排序过程需要进行的元素之间的比较次数都相同，为 $\sum_{i=2}^{n}(i-1)=\frac{n(n-1)}{2}$ 次。 - 适用情况：选择排序方法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，选择排序方法比较适合于参加排序序列的数据量较小的情况。选择排序的主要优点是仅需要原地操作无需占用其他空间就可以完成排序，因此在空间复杂度要求较高时，可以考虑选择排序。
- 排序稳定性：由于值最小元素与未排序部分第 1 个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变值相同元素的前后位置，因此，选择排序法是一种 不稳定排序算法。
- 对比冒泡排序：
class Solution: |
1.3 插入排序
插入排序（Insertion Sort）基本思想：将整个序列分为两部分：前面 i 个元素为有序序列，后面 n - i 个元素为无序序列。每一次排序，将无序序列的第 1 个元素，在有序序列中找到相应的位置并插入。
1.3.1 算法步骤
- 第
1趟排序：- 第
1个元素为有序序列，后面第2~n个元素（总共n - 1个元素）为无序序列。 - 从右至左遍历有序序列中的元素，如果遇到「有序序列的元素 > 无序序列的第
1个元素」的情况时，则将向有序序列的元素后移动一位。 - 如果遇到「有序序列的元素 <= 无序序列的第
1个元素」的情况或者「到达数组开始位置」时，则说明找到了插入位置。将「无序序列的第1个元素」插入该位置。
- 第
第
2趟排序：- 第
1~2个元素为有序序列，后面第3~n个元素（总共n - 2个元素）为无序序列。 - 从右至左遍历有序序列中的元素，如果遇到「有序序列的元素 > 无序序列的第
1个元素」的情况时，则将向有序序列的元素后移动一位。 - 如果遇到「有序序列的元素 <= 无序序列的第
1个元素」的情况或者「到达数组开始位置」时，则说明找到了插入位置。将「无序序列的第1个元素」插入该位置。
- 第
依次类推，对剩余
n - 3个元素重复上述排序过程，直到所有元素都变为有序序列，则排序结束。
简单来说，插入排序的算法步骤为：
- 先将第
1个元素作为一个有序序列，将第2~n个元素作为无序序列。 - 从左到右遍历一遍无序序列，对于无序序列中的每一个元素：
- 遍历有序序列，找到适当的插入位置。
- 将有序序列中插入位置右侧的元素依次右移一位。
- 将该元素插入到适当位置
动画演示：
1.3.2 算法分析
插入排序比对操作主要是用来寻找新元素的待插入位置，而插入位置是靠倒序遍历前面有序数组来找到的。
- 最佳时间复杂度：$O(n)$。
最好的情况下，初始序列已经是升序排列，这样每个新元素只需要进行一次元素之间的比较， 总共只需要比对n − 1次，也完全并不需要移动有序数组的元素，此时时间复杂度是$O(n)$ - 最差时间复杂度：$O(n^2)$。
最差的情况下，初始序列已经是降序排列，对应的每个i值都要进行i - 1次元素之间的比较，总的元素之间的比较次数达到最大值，为 $∑^n_{i=2}(i − 1) = \frac{n(n−1)}{2}$。 - 平均时间复杂度：$O(n^2)$。如果序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 $\frac{n^2}{4}$。由此得知，插入排序算法的时间复杂度 $O(n^2)$。
- 排序稳定性：插入排序方法是一种 稳定排序算法。
1.3.3 代码实现
也可以都改成for语句：class Solution:
def insertionSort(self, nums):
# 遍历无序序列
for i in range(1, len(nums)):
temp = nums[i] # 保存无序序列第一个元素的值，因为后面会有有序序列右移，覆盖此值
j = i # 初始化插入位置
# 从右至左遍历有序序列
# 如果有序序列中的元素大于无序序列第一个元素，就将其右移一位
while j > 0 and nums[j - 1] > temp:
nums[j] = nums[j - 1]
j -= 1
# 将该元素值插入到适当位置
nums[j] = temp
return nums
def sortnumsay(self, nums: List[int]) -> List[int]:
return self.insertionSort(nums)class Solution:
def insertionSort(self, nums):
# 遍历无序序列
for i in range(1, len(nums)):
temp = nums[i] # 保存当前元素值
# 从右至左遍历有序序列
for j in range(i,-1,-1):
if nums[j - 1] > temp:
# 将有序序列中插入位置右侧的元素依次右移一位
nums[j] = nums[j - 1]
else:
break
# 将该元素插入到适当位置
nums[j] = temp
return nums
def sortnumsay(self, nums: List[int]) -> List[int]:
return self.insertionSort(nums)1.4 希尔排序
从上面分析可以知道，插入排序在初始序列升序排列时，时间复杂度最低。实际上，序列越是有序（升序），插入排序的比对次数就越少。
希尔排序从此入手，对无序列表进行间隔划分，然后对每个子列表进行插入排序。随着子列表数越来越少，整个无序表也越来越有序，从而减少整体排序的比对次数。
希尔排序（Shell Sort）基本思想：将整个序列切按照一定的间隔值（gap）划分为若干个子序列，每个子序列分别排序。然后逐渐缩小gap值，进行下一次排序，直至gap=1。
1.4.1 算法步骤
- 确定一个元素间隔数
gap。 - 将参加排序的序列按此间隔数从第
1个元素开始一次分成若干个子序列，即分别将所有位置相隔为gap的元素视为一个子序列。 - 在各个子序列中采用某种排序算法（例如插入排序算法）进行排序。
- 减少间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序。依次类推，直到间隔数
gap = 1，排序结束。
图解演示：
1.4.2 算法分析
时间复杂度：介于 $O(n \times \log_2 n)$ 与 $O(n^2)$ 之间。
- 希尔排序方法的速度是一系列间隔数 $gap_i$ 的函数，而比较次数与 $gap_i$ 之间的依赖关系比较复杂，不太容易给出完整的数学分析。
- 由于采用 $gapi = \lfloor gap{i-1}/2 \rfloor$ 的方法缩小间隔数，对于具有 $n$ 个元素的序列，若 $gap_1 = \lfloor n/2 \rfloor$，则经过 $p = \lfloor \log_2 n \rfloor$ 趟排序后就有 $gap_p = 1$，因此，希尔排序方法的排序总躺数为 $\lfloor \log_2 n \rfloor$。
- 从算法中也可以看到，最外层的
while循环为 $\log_2 n$ 数量级，中间层do-while循环为n数量级。当子序列分得越多时，子序列内的元素就越少，最内层的for循环的次数也就越少；反之，当所分的子序列个数减少时，子序列内的元素也随之增多，但整个序列也逐步接近有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在 $O(n \times \log_2 n)$ 与 $O(n^2)$ 之间。
排序稳定性：希尔排序方法是一种 不稳定排序算法。
1.4.3 代码实现：
class Solution: |
1.5 归并排序
归并排序（Merge Sort）基本思想：采用经典的分治策略，先递归地将当前序列平均分成两半。然后将有序序列两两合并，最终合并成一个有序序列。
1.5.1 算法步骤
- 分割过程：先递归地将当前序列平均分成两半，直到子序列长度为 1。
- 找到序列中心位置
mid，从中心位置将序列分成左右两个子序列left_arr、right_arr。 - 对左右两个子序列
left_arr、right_arr分别进行递归分割。 - 最终将数组分割为 n 个长度均为 1 的有序子序列。
- 找到序列中心位置
- 归并过程：从长度为 1 的有序子序列开始，依次进行两两归并，直到合并成一个长度为 n 的有序序列。
- 使用数组变量
arr存放归并后的有序数组。 - 使用两个指针
left、right分别指向两个有序子序列 left_arr、right_arr 的开始位置。 - 比较两个指针指向的元素，将两个有序子序列中较小元素依次存入到结果数组
arr中，并将指针移动到下一位置。 - 重复步骤 3，直到某一指针到达子序列末尾。
- 将另一个子序列中的剩余元素存入到结果数组
arr中。 - 返回归并后的有序数组
arr。
- 使用数组变量
动画演示：
- 将序列分为为 [6]，[2]，[1]，[3]，[7]，[5]，[4]，[8]。
- 第 1 趟排序：将子序列中的有序子序列两两归并，归并后的子序列为：[2, 6]，[1, 3]，[5, 7]，[4, 8]。
- 第 2 趟排序：将子序列中的有序子序列两两归并，归并后的子序列为：[1, 2, 3, 6]，[4, 5, 7, 8]。
- 第 3 趟排序：将子序列中的有序子序列两两归并，归并后的子序列为：[1, 2, 3, 4, 5, 6, 7, 8]。得到长度为 n 的有序序列，排序结束。
1.5.2 算法分析
- 时间复杂度：$O(n \times \log_2n)$。归并排序算法的时间复杂度等于归并趟数与每一趟归并的时间复杂度乘积。子算法
merge(left_arr, right_arr):的时间复杂度是 $O(n)$，因此，归并排序算法总的时间复杂度为 $O(n \times \log_2 n)$。 - 空间复杂度：$O(n)$。归并排序方法需要用到与参加排序的序列同样大小的辅助空间。因此算法的空间复杂度为 $O(n)$。
- 排序稳定性：归并排序算法是一种 稳定排序算法。
- 因为在两个有序子序列的归并过程中，如果两个有序序列中出现相同元素，
merge(left_arr, right_arr):算法能够使前一个序列中那个相同元素先被复制，从而确保这两个元素的相对次序不发生改变。1.5.3 代码实现：
class Solution(object):
def sortArray(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return self.merge(nums)
def merge(self,arr): # 分割过程
if len(arr)<=1:
return arr # 数组元素个数小于等于 1 时，直接返回原数组
mid=len(arr)//2
# 注意，这里是递归的写法
left_arr=self.merge(arr[:mid])
right_arr=self.merge(arr[mid:])
return self.mergesort(left_arr,right_arr)
def mergesort(self,left_arr,right_arr): # 归并过程
left,right=0,0
arr=[]
# 将两个有序子序列中较小元素依次插入到结果数组中
# 注意，这里都是<，不能取=,因为left_arr[len(left_arr)]是超出索引的
while left<len(left_arr) and right<len(right_arr):
if left_arr[left]<right_arr[right]:
arr.append(left_arr[left])
left+=1
else:
arr.append(right_arr[right])
right+=1
# 如果子序列有剩余元素，则将其插入到结果数组中
arr=arr+left_arr[left:]+right_arr[right:]
return arr1.6 快速排序
快速排序（Quick Sort）基本思想： 根据序列的中值将序列分为两半，前一半都小于中值，后一半都大于中值，然后每部分再进行递归的快速排序。1.6.1 算法步骤
递归结束条件：序列只有一个元素，不需要再排序
中值选取：每次根据中值将序列分为规模相等的两半是最好的情况，此时中值就是序列的中位数，但是寻找中位数也需要开销，所以可以所以找一个数作为中值，比如序列的第一个数。
- 因为在两个有序子序列的归并过程中，如果两个有序序列中出现相同元素，
分裂过程： 目标是找到“中值”的位置。
- 设置左右标(left/right)
- 左标向右移动，右标向左移动
- 左标一直向右移动，碰到比中值大的就停止；右标一直向左移动，碰到比中值小的就停止。然后把左右标所指的数据项交换，
- 继续移动，直到左标移到右标的右侧，停止移动。这时右标所指位置就是“中值”应处的位置，将中值和这个位置交换，并记录此时中值的位置。这样就分裂完成，左半部分比中值小，右半部分比中值大。
- 图解演示：
动画演示：
1.6.2 算法分析
快速排序算法的时间复杂度主要跟基准数的选择有关。本文中是将当前序列中第1个元素作为基准值。在这种选择下，如果参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。也就是会得到最坏时间复杂度。
在这种情况下，第 1 趟排序经过 n - 1 次比较以后，将第 1 个元素仍然确定在原来的位置上，并得到 1 个长度为 n - 1 的子序列。第 2 趟排序进过 n - 2 次比较以后，将第 2 个元素确定在它原来的位置上，又得到 1 个长度为 n - 2 的子序列。
最终总的比较次数为 $(n − 1) + (n − 2) + … + 1 = \frac{n(n − 1)}{2}$。因此这种情况下的时间复杂度为 $O(n^2)$，也是最坏时间复杂度，这种情况一般不会发生。
而在平均情况下，我们可以从当前序列中随机选择一个元素作为基准数。这样，每一次选择的基准数可以看做是等概率随机的。其期望时间复杂度为 $O(n \times \log_2n)$，也就是平均时间复杂度。
下面来总结一下：
- 最佳时间复杂度：$O(n \times \log_2n)$。每一次选择的基准数都是当前序列的中位数，此时算法时间复杂度满足的递推式为 $T(n) = 2 \times T(\frac{n}{2}) + \Theta(n)$，由主定理可得 $T(n) = O(n \times \log_2n)$。
- 最坏时间复杂度：$O(n^2)$。每一次选择的基准数都是序列的最终位置上的值，此时算法时间复杂度满足的递推式为 $T(n) = T(n - 1) + \Theta(n)$，累加可得 $T(n) = O(n^2)$。
- 平均时间复杂度：$O(n \times \log_2n)$。在平均情况下，每一次选择的基准数可以看做是等概率随机的。其期望时间复杂度为 $O(n \times \log_2n)$。
- 空间复杂度：$O(n)$。无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序序列的首、尾位置。最坏的情况下，空间复杂度为 $O(n)$。如果对算法进行一些改写，在一趟排序之后比较被划分所得到的两个子序列的长度，并且首先对长度较短的子序列进行快速排序，这时候需要的空间复杂度可以达到 $O(log_2 n)$。
- 排序稳定性：快速排序是一种 不稳定排序算法。
1.6.3 代码实现：
从待排序列中找到一个基准数pivot（这里取序列第一个元素），将比pivot小的元素都移到序列左侧，比pivot大的都移到序列右侧。这样就将待排序列分成了[start,pivot-1]、pivot和[pivot+1,end]三部分。再分别对前后两部分递归调用快速排序。也可以写成另一种方式：def quickSort(nums):
return qSort(nums,0,len(nums)-1)
def qSort(nums,start,end):
if start<end:
"""
当分裂后的子序列有两个以上元素时，就进行排序。
使用左右指针分别指向子序列的开头和结尾
"""
pivot=nums[start]
left,right=start+1,end
done=True
"""
左指针一直右移，直到指向的元素大于中值；右指针一直左移，直到指向的元素小于中值。交换左右指针的元素值
继续下一次移动交换，直到左指针越过右指针。此时右指针位置就是中值应该在的位置，进行交换，排序完毕。
"""
while done:
while left<=right and nums[left]<=pivot:
left=left+1
while left<=right and nums[right]>=pivot:
right=right-1
if left>right:
done=False
else:
nums[left],nums[right] = nums[right],nums[left]
nums[start],nums[right]=nums[right],nums[start]
"""
排完序后，中值前的部分[start,pivot-1]都是小于中值，中值后的部分[pivot+1,end]都是大于中值
对这两部分再次进行递归的快速排序
"""
qSort(nums,start,right-1)
qSort(nums,right+1,end)
return nums
class Solution(object): |
1.7 桶排序
桶排序（Bucket Sort）基本思想：将未排序数组分到若干个「桶」中，每个桶的元素再进行单独排序。
1.7.1 算法步骤
- 根据原始数组的值域范围，将数组划分为
k个相同大小的子区间，每个区间称为一个桶。 - 遍历原始数组元素，将每个元素装入对应区间的桶中。
- 对每个桶内的元素单独排序（使用插入排序、归并排序、快排排序等算法）。
- 最后按照区间顺序将桶内的元素合并起来，完成排序。
图解演示
- 划分子区间
- 将数组元素装入桶中，并对桶内元素单独排序
- 将桶内元素合并起来，完成排序
1.7.2 算法分析
- 时间复杂度：$O(n)$。当输入元素个数为 $n$，桶的个数是 $m$ 时，每个桶里的数据就是 $k = n / m$ 个。每个桶内排序的时间复杂度为 $O(k \times \log_2 k)$。$m$ 个桶就是 $m O(k log_2k) = m \times O((n / m) \times \log_2(n/m)) = O(n*log_2(n/m))$。当桶的个数 $m$ 接近于数据个数 $n$ 时，$log_2(n/m)$ 就是一个较小的常数，所以排序桶排序时间复杂度接近于 $O(n)$。
- 空间复杂度：$O(n + m)$。由于桶排序使用了辅助空间，所以桶排序的空间复杂度是 $O(n + m)$。
- 排序稳定性：如果桶内使用插入排序算法等稳定排序算法，则桶排序也是一种 稳定排序算法。
1.7.3 代码实现
class Solution: |
1.8 堆排序
1.8.1 算法思想
堆排序（Heap sort）基本思想：
借用「堆结构」所设计的排序算法。将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆结构继续维持大顶堆性质。
堆（Heap）：符合以下两个条件之一的完全二叉树：
- 大顶堆：根节点值 ≥ 子节点值。
- 小顶堆：根节点值 ≤ 子节点值。
1.8.2 算法步骤
- 建立初始堆：将无序序列构造成第
1个大顶堆（初始堆），使得n个元素的最大值处于序列的第1个位置。 - 调整堆：交换序列的第
1个元素（最大值元素）与第n个元素的位置。将序列前n - 1个元素组成的子序列调整成一个新的大顶堆，使得n - 1个元素的最大值处于序列第1个位置，从而得到第2个最大值元素。 - 调整堆：交换子序列的第
1个元素（最大值元素）与第n - 1个元素的位置。将序列前n - 2个元素组成的子序列调整成一个新的大顶堆，使得n - 2个元素的最大值处于序列第1个位置，从而得到第3个最大值元素。 - 依次类推，不断交换子序列的第
1个元素（最大值元素）与当前子序列最后一个元素位置，并将其调整成新的大顶堆。直到子序列剩下一个元素时，排序结束。此时整个序列就变成了一个有序序列。
从堆排序算法步骤中可以看出：堆排序算法主要涉及「调整堆」和「建立初始堆」两个步骤。
1.8.3 调整堆
调整堆方法：把移走了最大值元素以后的剩余元素组成的序列再构造为一个新的堆积。具体步骤如下：
- 从根节点开始，自上而下地调整节点的位置，使其成为堆积。
- 判断序号为
i的节点与其左子树节点（序号为2 * i）、右子树节点（序号为2 * i + 1）中值关系。 - 如果序号为
i节点大于等于左右子节点值，则排序结束。 - 如果序号为
i节点小于左右子节点值，则将序号为i节点与左右子节点中值最大的节点交换位置。
- 判断序号为
- 因为交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是，从当前节点的左右子树节点开始，自上而下继续进行类似的调整。
- 依次类推，直到整棵完全二叉树成为一个大顶堆。
调整堆方法演示
- 交换序列的第
1个元素90与最后1个元素19的位置，此时当前节点为根节点19。 - 判断根节点
19与其左右子节点值，因为17 < 19 < 36，所以将根节点19与左子节点36互换位置，此时当前节点为根节点19。 - 判断当前节点
36与其左右子节点值，因为19 < 25 < 26，所以将当前节点19与右节点26互换位置。调整堆结束。
1.8.4 建立初始堆
- 如果原始序列对应的完全二叉树（不一定是堆）的深度为
d，则从d - 1层最右侧分支节点（序号为 $\lfloor \frac{n}{2} \rfloor$）开始，初始时令 $i = \lfloor \frac{n}{2} \rfloor$，调用调整堆算法。 - 每调用一次调整堆算法，执行一次
i = i - 1，直到i == 1时，再调用一次，就把原始序列调整为了一个初始堆。
方法演示
- 原始序列为
[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]，对应完全二叉树的深度为3。 - 从第
2层最右侧的分支节点，也就序号为5的节点开始，调用堆调整算法，使其与子树形成大顶堆。 - 节点序号减
1，对序号为4的节点，调用堆调整算法，使其与子树形成大顶堆。 - 节点序号减
1，对序号为3的节点，调用堆调整算法，使其与子树形成大顶堆。 - 节点序号减
1，对序号为2的节点，调用堆调整算法，使其与子树形成大顶堆。 - 节点序号减
1，对序号为1的节点，调用堆调整算法，使其与子树形成大顶堆。 - 此时整个原始序列对应的完全二叉树就成了一个大顶堆，建立初始堆完毕。
1.8.5 堆排序方法完整演示
- 原始序列为
[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]，先根据原始序列建立一个初始堆。 - 交换序列中第
1个元素（90）与第10个元素（2）的位置。将序列前9个元素组成的子序列调整成一个大顶堆，此时堆顶变为36。 - 交换序列中第
1个元素（36）与第9个元素（3）的位置。将序列前8个元素组成的子序列调整成一个大顶堆，此时堆顶变为26。 - 交换序列中第
1个元素（26）与第8个元素（2）的位置。将序列前7个元素组成的子序列调整成一个大顶堆，此时堆顶变为25。 - 以此类推，不断交换子序列的第
1个元素（最大值元素）与当前子序列最后一个元素位置，并将其调整成新的大顶堆。直到子序列只剩下最后一个元素1时，排序结束。此时整个序列变成了一个有序序列，即[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]。
1.8.6 堆排序算法分析
- 时间复杂度：$O(n \times \log_2 n)$。
- 堆积排序的时间主要花费在两个方面：「建立初始堆」和「调整堆」。
- 设原始序列所对应的完全二叉树深度为 $d$，算法由两个独立的循环组成：
- 在第 $1$ 个循环构造初始堆积时，从 $i = d - 1$ 层开始，到 $i = 1$ 层为止，对每个分支节点都要调用一次调整堆算法，而一次调整堆算法，对于第 $i$ 层一个节点到第 $d$ 层上建立的子堆积，所有节点可能移动的最大距离为该子堆积根节点移动到最后一层（第 $d$ 层） 的距离，即 $d - i$。而第 $i$ 层上节点最多有 $2^{i-1}$ 个，所以每一次调用调整堆算法的最大移动距离为 $2^{i-1} * (d-i)$。因此，堆积排序算法的第 $1$ 个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和，即：$\sum{i = d - 1}^1 2^{i-1} (d-i) = \sum{j = 1}^{d-1} 2^{d-j-1} \times j = \sum{j = 1}^{d-1} 2^{d-1} \times {j \over 2^j} \le n \sum{j = 1}^{d-1} {j \over 2^j} < 2n$。这一部分的时间花费为 $O(n)$。
- 在第 $2$ 个循环中，每次调用调整堆算法一次，节点移动的最大距离为这棵完全二叉树的深度 $d = \lfloor \log_2(n) \rfloor + 1$，一共调用了 $n - 1$ 次调整堆算法，所以，第 $2$ 个循环的时间花费为 $(n-1)(\lfloor \log_2 (n)\rfloor + 1) = O(n \times \log_2 n)$。
- 因此，堆积排序的时间复杂度为 $O(n \times \log_2 n)$。
- 空间复杂度：$O(1)$。由于在堆积排序中只需要一个记录大小的辅助空间，因此，堆积排序的空间复杂度为：$O(1)$。
- 排序稳定性：堆排序是一种 不稳定排序算法。
1.8.7 代码实现
class Solution: |
1.9 计数排序
计数排序（Counting Sort）基本思想：使用一个额外的数组 counts，其中 counts[i] 表示原数组 arr 中值等于 i 的元素个数。然后根据数组 counts 来将 arr 中的元素排到正确的位置。
1.9.1 算法步骤
- 找出待排序序列中最大值元素
arr_max和最小值元素arr_min。 - 定义大小为
arr_max - arr_min + 1的数组counts，初始时，counts中元素值全为0。 - 遍历数组
arr，统计值为num的元素出现的次数。将其次数存入counts数组的第num - arr_min项（counts[num - arr_min]表示元素值num出现的次数）。 - 对所有的计数累加，从
counts中的第一个元素开始，每一项和前一项相加。此时counts[i]表示值为i的元素排名。 - 反向填充目标数组：
- 逆序遍历数组
arr。对于每个元素值arr[i]，其对应排名为counts[arr[i] - arr_min]。 - 根据排名，将
arr[i]放在数组对应位置（因为数组下标是从0开始的，所以对应位置为排名减1）。即res[counts[arr[i] - arr_min] - 1] = arr[i]。 - 放入之后， 将
arr[i]的对应排名减1，即counts[arr[i] - arr_min] -= 1。
- 逆序遍历数组
动画演示
1.9.2 算法分析
- 时间复杂度：$O(n + k)$。其中 $k$ 代表待排序序列的值域。
- 空间复杂度：$O(k)$。其中 $k$ 代表待排序序列的值域。由于用于计数的数组
counts的长度取决于待排序数组中数据的范围（大小等于待排序数组最大值减去最小值再加1）。所以计数排序算法对于数据范围很大的数组，需要大量的内存。 - 计数排序适用情况：计数排序一般用于整数排序，不适用于按字母顺序、人名顺序排序。
- 排序稳定性：计数排序是一种 稳定排序算法。
1.9.3. 代码实现
class Solution: |
1.10 基数排序
假设要对 10 万个手机号码进行排序，显然桶排序和计数排序都不太适合，那怎样才能做到时间复杂度为 O(n) 呢? 此时可以考虑基数排序。
手机号码有这样的规律，假设要比较两个手机号码 a, b 的大小，如果在前面几位中，a 手机号码已经比 b大了，那后面几位就不用看了。所以借助 稳定排序算法，我们可以这么实现：从手机号码的最后一位开始，分别按照每一位的数字对手机号码进行排序，依次往前进行，经过 11 次排序之后，手机号码就都有序了。
基数排序（Radix Sort）基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后后，从最低位开始，依次进行排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
1.10.1 算法步骤
基数排序算法可以采用「最低位优先法（Least Significant Digit First）」或者「最高位优先法（Most Significant Digit first）」。最常用的是「最低位优先法」。
下面我们以最低位优先法为例，讲解一下算法步骤。
- 遍历数组元素，获取数组最大值元素，并取得位数。
- 定义一个长度为
10的桶buckets，分别代表0 ~ 9这10位数字。 - 以个位元素为索引，根据数组元素个位上的值，将数组元素存入对应数字的桶中。
- 清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。
- 之后分别以十位，百位，…，最大值元素的最高位为索引，根据元素对应位上的数字，存入对应数字的桶中。并合并数组，完成排序。
动画演示
- 初始序列为
[32, 1, 10, 96, 57, 7, 62, 47, 82, 25, 79, 5]，序列所有元素的最大位数为2。 - 以个位为索引，根据元素个位上的数字，将其分别存入到
0~9这10个桶中。 - 清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。此时序列变为
[10, 1, 32, 62, 82, 25, 5, 96, 57, 7, 47, 79]。 - 以十位为索引，根据元素十位上的数字，将其分别存入到
0~9这10个桶中。 - 清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。此时序列变为
[1, 5, 7, 10, 25, 32, 47, 57, 62, 79, 82, 96]，完成排序。
1.10.2 算法分析
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
- 时间复杂度：$O(n \times k)$。
- 根据每一位的排序，可以用桶排序或者计数排序来实现，它们的时间复杂度可以做到 O(n)。如果排序的数据有 K位，则总的时间复杂度为 O(K * n)，当 K 不大时，基数排序的时间复杂度就近似为 O(n)
- $k$ 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。
- 空间复杂度：$O(n + k)$。
- 排序稳定性：基数排序是一种 稳定排序算法。
- 有时候，要排序的数据并不都是等长的，比如我们要对英文单词进行排序。这时候，我们可以把所有单词都补足到相同长度，位数不够的在后面补 ’0‘，所有字母的 ASCII 码都大于 ‘0’，因此不会影响原有的大小顺序。
1.10.3 代码实现
class Solution: |
1.11 排序算法总结
下面为七种经典排序算法指标对比情况：
冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为logn(因为递归调用了)
- 归并排序空间复杂是O(n),需要一个大小为n的临时数组.。基数排序的空间复杂是O(n),桶排序的空间复杂度不确定。
- 所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)。但桶排序一般用的不多,因为有几个比较大的缺陷.
- 待排序的元素不能是负数,小数.
- 空间复杂度不确定,要看待排序元素中最大值是多少.。所需要的辅助数组大小即为最大元素的值.
二、 练习题
2.1 移动零（题283）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
- 示例 1:
- 输入: nums = [0,1,0,3,12]
- 输出: [1,3,12,0,0]
- 示例 2:
- 输入: nums = [0]
- 输出: [0]
思路 1：冒泡排序（超时）
冒泡排序的思想，就是通过相邻元素的比较与交换，使得较大元素从前面移到后面。我们可以借用冒泡排序的思想，将值为 0 的元素移动到数组末尾。因为冒泡排序的时间复杂度为$O(n^2)$ 。所以这种做法会导致超时。
思路 2：双指针
- 使用两个指针 slow，fast。slow 指向处理好的非 0 数字数组的尾部，fast 指针指向当前待处理元素。
- 不断向右移动 fast 指针，每次移动到非零数，则将左右指针对应的数交换，交换同时将 slow 右移。
- 此时，slow 指针左侧均为处理好的非零数，而从 slow 指针指向的位置开始， fast 指针左边为止都为 0。
- 遍历结束之后，则所有 0 都移动到了右侧，且保持了非零数的相对位置。
class Solution: |
2.2 颜色分类（题75）
方法一：单指针
这道题和上一题很类似，最简单的方法是遍历两次，先将0排到最前面，再接着将1排到前面：
class Solution: |
方法二：双指针（官方题解）
我们可以额外使用一个指针，即使用两个指针分别用来交换 0 和1。具体地，我们用指针 $p_0$来交换 0，$p_1$来交换 1，初始值都为 0。当我们从左向右遍历整个数组时：
- 如果找到了 1，那么将其与 $nums[p_1]$ 进行交换，并将 $p_1$向后移动一个位置，这与方法一是相同的；
- 如果找到了 0，那么将其与 $nums[p_0]$ 进行交换，并将 $p_0$向后移动一个位置。这样做是正确的吗？
我们可以注意到，因为连续的 0 之后是连续的 1，因此如果我们将 0 与$nums[p_0]$ 进行交换，那么我们可能会把一个 1 交换出去。当 $p_0 < p_1$时，我们已经将一些 1 连续地放在头部，此时一定会把一个 1 交换出去，导致答案错误。因此，如果$p_0 < p_1$，那么我们需要再将 $nums[i]$ 与$nums[p_1]$进行交换，其中 i 是当前遍历到的位置。
在进行了第一次交换后，$nums[i]$的值为 1，我们需要将这个 1 放到「头部」的末端。在最后，无论是否有 $p_0 < p_1$，我们需要将 $p_0$ 和 $p_1$均向后移动一个位置，而不是仅将 $p_0$向后移动一个位置。
class Solution: |
方法三：快速排序
我们也可以借鉴快速排序算法中的 partition 过程，将 1 作为基准数 pivot，然后将序列分为三部分：0（即比 1 小的部分）、等于 1 的部分、2（即比 1 大的部分）。具体步骤如下：
- 使用两个指针 left、right，分别指向数组的头尾。left 表示当前处理好红色元素的尾部，right 表示当前处理好蓝色的头部。
- 再使用一个下标 index 遍历数组，如果遇到
nums[index] == 0，就交换 nums[index] 和 nums[left]，同时将 left 右移。如果遇到nums[index] == 2，就交换 nums[index] 和 nums[right]，同时将 right 左移。 - 直到 index 移动到 right 位置之后，停止遍历。遍历结束之后，此时 left 左侧都是红色，right 右侧都是蓝色。
- 注意：移动的时候需要判断 index 和 left 的位置，因为 left 左侧是已经处理好的数组，所以需要判断 index 的位置是否小于 left，小于的话，需要更新 index 位置。
class Solution: |
2.3 数组中的第K个最大元素（题215）
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。示例：
- 输入: [3,2,1,5,6,4], k = 2
- 输出: 5
这道题使用改进的冒泡排序、选择排序、插入排序都会超时。希尔排序（1440ms）、归并排序（1016ms）、堆排序（640ms），这些都是可以通过的。也可以考虑使用快速排序。
2.3.1 快速排序
快速排序思路：
使用快速排序在每次调整时，都会确定一个元素的最终位置，且以该元素为界限，将数组分成了左右两个子数组，左子数组中的元素都比该元素小，右子树组中的元素都比该元素大。
这样，只要某次划分的元素位置q恰好是第 k 个下标就找到了答案。至于nums[left,q-1]和nums[q+1,right]是否有序，我们并不关心。具体来说，在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 nums[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。
class Solution(object): |
使用完整的快速排序再取第k大的元素，是2672ms。只排到第k大的元素是640ms。加上随机选取中值之后，是80ms到90ms。
堆排序、优先队列等方法可参考算法通关手册或官方题解。
与这道题类似的还有最小的k个数（剑指 Offer 40），使用随机快速排序：
class Solution(object): |
- 时间复杂度：$O(n)$。证明过程可参考「算法导论 9.2：期望为线性的选择算法」。
- 空间复杂度：$O(\log_2 n)$。递归使用栈空间的空间代价期望为 $O(\log_2n)$。
2.3.2 堆排序
升序堆排序的思路如下：
将无序序列构造成第
1个大顶堆（初始堆），使得n个元素的最大值处于序列的第1个位置。调整堆：交换序列的第
1个元素（最大值元素）与第n个元素的位置。将序列前n - 1个元素组成的子序列调整成一个新的大顶堆，使得n - 1个元素的最大值处于序列第1个位置，从而得到第2个最大值元素。调整堆：交换子序列的第
1个元素（最大值元素）与第n - 1个元素的位置。将序列前n - 2个元素组成的子序列调整成一个新的大顶堆，使得n - 2个元素的最大值处于序列第1个位置，从而得到第3个最大值元素。依次类推，不断交换子序列的第
1个元素（最大值元素）与当前子序列最后一个元素位置，并将其调整成新的大顶堆。直到获取第k个最大值元素为止。
代码：
class Solution: |
复杂度分析
- 时间复杂度：$O(n \times \log_2n)$。
- 空间复杂度：$O(1)$。
2.3.3 优先队列
- 遍历数组元素，对于挡圈元素
num：- 如果优先队列中的元素个数小于
k个，则将当前元素num放入优先队列中。 - 如果优先队列中的元素个数大于等于
k个，并且当前元素num大于优先队列的队头元素，则弹出队头元素，并将当前元素num插入到优先队列中。
- 如果优先队列中的元素个数小于
- 遍历完，此时优先队列的队头元素就是第K个最大元素，将其弹出并返回即可。
这里我们借助了 Python 中的 heapq 模块实现优先队列算法，这一步也可以通过手写堆的方式实现优先队列。
代码
import heapq |
复杂度分析
- 时间复杂度：$O(n \times \log_2k)$。
- 空间复杂度：$O(k)$。
2.4 排序数组（题912）
给你一个整数数组 nums，请你将该数组升序排列。
本题冒泡排序（改进）是过不了的，估计选择排序、插入排序也不行。可行的有希尔排序（1172ms）、归并排序（1036ms）、快速排序（816ms）。其中，验证的nums列表中有一个是nums全部为2的极端情况，直接快速排序是超时的。所以可以设置归并+快排，例如：
class Solution(object): |
其它排序方法详见算法通关手册。
2.5 数组中的逆序对（剑指 Offer 51）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例：
- 输入: [7,5,6,4]
- 输出: 5
思路 1：归并排序
归并排序主要分为：「分解过程」和「合并过程」。其中「合并过程」实质上是两个有序数组的合并过程。
每当遇到 左子数组当前元素 > 右子树组当前元素时，意味着「左子数组从当前元素开始，一直到左子数组末尾元素」与「右子树组当前元素」构成了若干个逆序对。
比如上图中的左子数组 [0, 3, 5, 7] 与右子树组 [1, 4, 6, 8]，遇到左子数组中元素 3 大于右子树组中元素 1。则左子数组从 3 开始，经过 5 一直到 7，与右子数组当前元素 1 都构成了逆序对。即 [3, 1]、[5, 1]、[7, 1] 都构成了逆序对。
因此，我们可以在合并两个有序数组的时候计算逆序对。具体做法如下：
- 使用全局变量
count来存储逆序对的个数。然后进行归并排序。 - 归并过程中：
- 使用数组变量 arr 存放归并后的有序数组
- 使用两个指针 left、right 分别指向两个有序子序列 left_arr、right_arr 的开始位置。
- 如果
left_arr[left] <= right_arr[right]，则将left_arr[left]存入到结果数组arr中，并将指针移动到下一位置。 - 如果
left_arr[left] > right_arr[right]，则 记录当前左子序列中元素与当前右子序列元素所形成的逆序对的个数，并累加到count中，即self.count += len(left_arr) - left，然后将right_arr[right]存入到结果数组arr中，并将指针移动到下一位置。 - 重复以上，直到某一指针到达子序列末尾，将另一个子序列中的剩余元素存入到结果数组 arr 中。
class Solution(object): |
思路 2 树状数组： 见算法通关手册
2.6 计算右侧小于当前元素的个数（题315）
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
- 示例 1：
- 输入：nums = [5,2,6,1]
- 输出：[2,1,1,0]
- 解释：
- 5 的右侧有 2 个更小的元素 (2 和 1)
- 2 的右侧仅有 1 个更小的元素 (1)
- 6 的右侧有 1 个更小的元素 (1)
- 1 的右侧有 0 个更小的元素
- 示例 2：
- 输入：nums = [-1]
- 输出：[0]
2.6.1 归并排序
这题类似上一题求逆序对。但是本题我们要求解的是nums[i]右侧小于nums[i]的元素的数量，即以nums[i]为左端点的「逆序对」的数目。注意到，在常规的归并排序过程中，数组中的元素其位置会发生变化，所以在本题中我们则需要记录下每个元素的初始位置，以便将每个元素贡献的逆序对数目归功到对应的位置上。
由于数组中的元素会重复，不能使用哈希表，所以考虑为每个数值添加其对应的下标，即对于第i个元素nums[i]，可将其扩充为(nums[i], i)。这样在nums排序过程中，即便 nums 中元素的位置发生了变化，也可将每个元素贡献的逆序对数目准确定位到对应的位置上，原理如下图所示：
class Solution: |
2.6.2 有序数组 （Sorted List）+ 二分搜索
基本思路： 维护一个有序数组 sl，从右往左依次往里添加 nums 中的元素，每次添加 nums[i] 前基于「二分搜索」判断出当前 sl 中比 nums[i] 小的元素个数（即 nums[i] 右侧比 nums[i] 还要小的元素个数），并计入答案即可。
class Solution: |
可简写为：
from sortedcontainers import SortedList |
树状数组、线段树方法，请参考《『 4种解法一网打尽 』 有序数组、归并排序、树状数组和线段树的实现及注释》。
2.7 最大间距 （题164）
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
示例 :
- 输入: nums = [3,6,9,1]
- 输出: 3
- 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
- 提示：$1 <= nums.length <= 10^5$，$0 <= nums[i] <= 10^9$
2.7.1 基数排序
根据题意可知所有元素都是非负整数，且数值在 32 位有符号整数范围内。所以我们可以选择基数排序。基数排序的步骤如下：
- 遍历数组元素，获取数组最大值元素，并取得位数。
- 以个位元素为索引，对数组元素排序。
- 合并数组。
- 之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，进行排序，并合并数组，最终完成排序。
- 最后，还要注意数组元素个数小于 2 的情况需要特别判断一下。
class Solution: |
复杂度分析
- 时间复杂度：O(N)
- 空间复杂度：O(N)。
2.7.2 桶排序
例如：nums = [1,3,4,5,6,10,11,12,17]
则：每个桶的长度 = （17 - 1） / (9-1) = 2。桶的个数 = （17-1）/ 2 + 1 = 9
所以我们的桶为（左闭右开）：
答案 = max（差值） = 5。
注意：在桶长度这里我们进行了和1取max的操作，这是为了一些边界条件的情况，比如数组是
[1,1,1,1]。当然我们也可以不取max，把向下取整改为向上取整。
在所有排序算法里，我们一般认为快速排序是速度相对较快的，然而桶排序在大多数情况下比快速排序还要快，但是它付出的代价就是牺牲O(n)空间的复杂度，且比归并排序的空间占用要多一点点，多出来的一点点就是可能出现的空桶。
class Solution: |
2.7.3 你的代码真是无敌了
class Solution(object): |
之前最快的是224ms。
2.8 数组的相对顺序（题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]
- 示例 2:
- 输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
- 输出：[22,28,8,6,17,44]
提示：1 <= arr1.length, arr2.length <= 1000；0 <= arr1[i], arr2[i] <= 1000
因为元素值范围在 [0, 1000]，所以可以使用计数排序的思路来解题。
- 使用数组 count 统计 arr1 各个元素个数。
- 遍历 arr2 数组，将对应元素num2 按照个数 count[num2] 添加到答案数组 ans 中，同时在 count 数组中减去对应个数。
- 然后在处理 count 中剩余元素，将 count 中大于 0 的元素下标依次添加到答案数组 ans 中。最后返回答案数组 ans
class Solution: |
2.9 存在重复元素 III（题220）
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。
- 示例 1：
- 输入：nums = [1,2,3,1], k = 3, t = 0
- 输出：true
- 示例2：
- 输入：nums = [1,5,9,1,5,9], k = 2, t = 3
- 输出：false
题目中需要满足两个要求，一个是元素值的要求（abs(nums[i] - nums[j]) <= t） ，一个是下标范围的要求（abs(i - j) <= k）。所以对于任意一个位置 i 来说，合适的 j 应该在区间 [i - k, i + k] 内，同时 nums[j] 值应该在区间 [nums[i] - t, nums[i] + t] 内。
检测相邻 2 * k 个元素是否满足 abs(nums[i] - nums[j]) <= t 的方法。有两种思路：「桶排序」和「滑动窗口（固定长度）」。
2.9.1 桶排序
- 利用桶排序的思想，将桶的大小设置为
t + 1。只需要使用一重循环遍历位置i，然后根据nums[i] // (t + 1)，从而决定将nums[i]放入哪个桶中。 - 这样在同一个桶内各个元素之间的差值绝对值都小于等于
t。而相邻桶之间的元素，只需要校验一下两个桶之间的差值是否不超过t。这样就可以以 $O(1)$ 的时间复杂度检测相邻2 * k个元素是否满足abs(nums[i] - nums[j]) <= t。 - 而
abs(i - j) <= k条件则可以通过在一重循环遍历时，将超出范围的nums[i - k]从对应桶中删除，从而保证桶中元素一定满足abs(i - j) <= k。
具体步骤如下：
- 将每个桶的大小设置为
t + 1。我们将元素按照大小依次放入不同的桶中。 - 遍历数组
nums中的元素，对于元素nums[i]：- 如果
nums[i]放入桶之前桶里已经有元素了，那么这两个元素必然满足abs(nums[i] - nums[j]) <= t， - 如果之前桶里没有元素，那么就将
nums[i]放入对应桶中。 - 再判断左右桶的左右两侧桶中是否有元素满足
abs(nums[i] - nums[j]) <= t。 - 然后将
nums[i - k]之前的桶清空，因为这些桶中的元素与nums[i]已经不满足abs(i - j) <= k了。
- 如果
- 最后上述满足条件的情况就返回
True，最终遍历完仍不满足条件就返回False。
代码
class Solution: |
复杂度分析
- 时间复杂度：$O(n)$。$n$ 是给定数组长度。
- 空间复杂度：$O(min(n, k))$。桶中最多包含 $min(n, k + 1)$ 个元素。
2.9.2滑动窗口（固定长度）
- 使用一个长度为
k的滑动窗口，每次遍历到nums[right]时，滑动窗口内最多包含nums[right]之前最多k个元素。只需要检查前k个元素是否在[nums[right] - t, nums[right] + t]区间内即可。 - 检查
k个元素是否在[nums[right] - t, nums[right] + t]区间，可以借助保证有序的数据结构（比如SortedList）+ 二分查找来解决，从而减少时间复杂度。
具体步骤如下：
- 使用有序数组类
window维护一个长度为k的窗口，满足数组内元素有序，且支持增加和删除操作。 left、right都指向序列的第一个元素。即：left = 0，right = 0。- 将当前元素填入窗口中，即
window.add(nums[right])。 - 当窗口元素大于
k个时，即right - left > k，移除窗口最左侧元素，并向右移动left。 - 当窗口元素小于等于
k个时：- 使用二分查找算法，查找
nums[right]在window中的位置idx。 - 判断
window[idx]与相邻位置上元素差值绝对值，若果满足abs(window[idx] - window[idx - 1]) <= t或者abs(window[idx + 1] - window[idx]) <= t时返回True。
- 使用二分查找算法，查找
- 向右移动
right。 - 重复
3~6步，直到right到达数组末尾，如果还没找到满足条件的情况，则返回False。
代码
from sortedcontainers import SortedList |
复杂度分析
- 时间复杂度：$O(n \times \log_2(min(n, k)))$。
- 空间复杂度：$O(min(n, k))$。
2.10 合并区间（题56）
给定数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
- 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出：[[1,6],[8,10],[15,18]]
- 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
- 输入：intervals = [[1,4],[4,5]]
- 输出：[[1,5]]
- 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
说明：
- $1 \le intervals.length \le 10^4$。
- $intervals[i].length == 2$。
- $0 \le starti \le endi \le 10^4$。
此题可以考虑对区间进行排序：
- 设定一个数组
ans用于表示最终不重叠的区间数组 - 对原始区间先按照区间左端点大小从小到大进行排序。
- 遍历所有区间，先将第一个区间加入
ans数组中。然后依次考虑后边的区间：- 如果第
i个区间左端点在前一个区间右端点右侧，则这两个区间不会重合，直接将该区间加入ans数组中。 - 否则的话，这两个区间重合，判断一下两个区间的右区间值，更新前一个区间的右区间值为较大值，然后继续考虑下一个区间，以此类推。
- 如果第
- 最后返回数组
ans。
代码class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for interval in intervals:
# not ans表示初始ans为空。ans[-1][1]是最后一个加入的区间的右端点
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else:
ans[-1][1] = max(ans[-1][1], interval[1])
return ans
- 时间复杂度：$O(n \times \log_2 n)$。其中 $n$ 为区间数量。
- 空间复杂度：$O(n)$。
2.11 最大数（题179）
2.11.1 自定义排序（内置函数）
本质上是给数组进行排序。假设 x、y 是数组 nums 中的两个元素，规定 排序判断规则 为：如果拼接字符串 x + y < y + x，则 y > x 。y 应该排在 x 前面。反之，则 y < x。
按照上述规则，对原数组套用任何方法进行排序即可。这里我们使用了 functools.cmp_to_key 自定义排序函数。
import functools |
- 时间复杂度：$O(n^2)$。其中 $n$ 为区间数量。
- 空间复杂度：$O(n)$。
类似的还有剑指 Offer 45. 把数组排成最小的数：
import functools |
2.11.2 自定义排序（快速排序）
class Solution: |