912. 排序数组

趁着这道题总结下排序方法

1.快速排序

算法描述

1.从数列中挑出一个元素，称为"基准"（pivot），
2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

class Solution:def sortArray(self, nums: List[int]) -> List[int]:def quick_sort(nums):# 特殊情况的处理if len(nums) <= 1:return nums# 哨兵元素k = random.choice(nums)# 初始化分区big, equal, small = [], [], []# 遍历数组，划分到各个分区for i in nums:if i > k:big.append(i)elif i == k:equal.append(i)else:small.append(i)# 对大的和小的继续递归dfs_big = quick_sort(big)dfs_small = quick_sort(small)return dfs_small + equal + dfs_bigreturn quick_sort(nums)

代码解释：

1. 基准情况：

   • 如果数组长度为1或为空，则直接返回。这是因为一个元素或空数组自然是有序的，不需要进一步排序。

2. 选择基准值：

   • 使用 random.choice(nums) 随机选择一个数组中的元素作为基准（pivot）。这种方法有助于避免快速排序在最坏情况下的性能问题，即当输入数组已经有序或接近有序时。

3. 分区：

   • 创建三个空列表：left（存储小于pivot的元素），middle（存储等于pivot的元素），right（存储大于pivot的元素）。
   • 遍历数组，根据元素值与pivot的比较结果，将每个元素放入相应的列表。

4. 递归排序：

   • 对 left 和 right 列表递归调用 quicksort 函数进行排序。

5. 合并结果：

   • 将排序后的 left、middle、和 right 列表合并，形成一个完整的排序后数组并返回。

2.冒泡排序

冒泡排序（Bubble Sort）是一种简单的算法>排序算法，它通过重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把它们交换过来。遍历数列的工作会重复进行，直到没有相邻元素需要交换为止，这表示该数列已经排序完成。

算法描述

1. 比较相邻的元素。如果第一个比第二个大（根据排序方向），就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法特点

• 性能：冒泡排序的平均时间复杂度和最坏时间复杂度都是 (O(n^2))，其中 (n) 是数组的长度。这是因为每次操作最多需要比较 (n-1) 对元素，并且需要重复 (n-1) 次这样的操作。
• 空间效率：冒泡排序是一个原地算法>排序算法，它只需要一个额外的存储空间来进行元素交换（即空间复杂度为 (O(1))）。
• 稳定性：冒泡排序是稳定的算法>排序算法，因为它确保不会改变相等元素的相对顺序。

应用场景

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

示例代码（Python）

def bubble_sort(arr):n = len(arr)for i in range(n-1):# 标记变量，用于优化排序过程swapped = Falsefor j in range(0, n-i-1):  # 最后i个元素已经排序好了if arr[j] > arr[j+1]:# 交换元素arr[j], arr[j+1] = arr[j+1], arr[j]swapped = True# 如果在这一轮遍历中没有交换过元素，则说明列表已经有序，可提前结束if not swapped:break

这段代码展示了冒泡排序的基本实现，并包含了一个小优化：如果在一轮遍历中没有进行任何交换，那么可以提前结束排序，因为这表示所有元素已经按顺序排列好了。这个优化有助于减少在已经排序好的数组上的不必要操作。
理论上，最后一个元素在最后一次外部循环之后已经在其正确位置，不需要再被包含在比较中，因此 n-1 次足够。

3.选择排序

选择排序是一种简单直观的比较算法>排序算法。它的工作原理是每次从未排序的部分找出最小（或最大，根据排序顺序）的元素，将它与未排序部分的起始位置元素交换。这个过程不断重复，直到整个数组排序完成。

算法步骤

选择排序的具体步骤如下：

1. 开始遍历：从数组的第一个元素开始，假设当前位置为已排序的。
2. 找最小值：在当前位置到数组末尾的未排序部分中找到最小值的元素。
3. 交换位置：将找到的最小元素与当前位置的元素交换。
4. 移动指针：移动到下一个位置，重复步骤2和3，直到到达数组的倒数第二个位置。

由于每次都要在未排序的部分找到最小（或最大）的元素，因此选择排序是不稳定的算法>排序算法，这意味着它可能会改变两个相等值的初始相对位置。

性能

• 时间复杂度：在最好、平均和最坏的情况下，选择排序的时间复杂度都是 (O(n^2))，其中 (n) 是数组的长度。这是因为选择排序的内层循环总是遍历未排序部分来找到最小元素。
• 空间复杂度：选择排序是一个原地算法>排序算法，它的空间复杂度为 (O(1))。

示例代码（Python）

下面是选择排序的一个标准实现：

def selection_sort(nums):n = len(nums)  # 获取数组的长度# 外层循环负责遍历数组的每个位置，确定该位置的正确元素for i in range(n):min_index = i  # 假设当前位置i是最小元素的索引# 内层循环从i+1开始，寻找真正的最小元素的索引for j in range(i+1, n):# 如果发现更小的元素，更新最小元素的索引if nums[j] < nums[min_index]:min_index = j# 将找到的最小元素放到它应该在的位置inums[i], nums[min_index] = nums[min_index], nums[i]  # 交换当前位置和最小元素的位置return nums  # 返回排序后的数组

特点和用途

• 简单：选择排序非常直观，容易理解和实现。
• 原地操作：不需要额外的存储空间。
• 不稳定：可能会因为交换操作改变相同元素之间的相对位置。
• 适用场景：由于其 (O(n^2)) 的时间复杂度，它适用于小数据集的排序。在数据规模较大时，其性能不如 (O(n\log n)) 的高级算法>排序算法（如快速排序、归并排序）。

选择排序的效率通常低于插入排序和冒泡排序，尤其是在处理大数据集时。然而，由于其原理简单和代码实现的直接性，它仍然是介绍算法>排序算法时的常用示例。

4.插入排序

算法思想

插入排序的基本思想是将一个数据元素（新的值）插入到一个已经排好序的序列中，并继续保持有序。每次循环从待排序的数据中取出第一个元素，将它插入到已经排序的序列中的适当位置，从而得到一个新的、元素个数增加1的有序序列。

算法步骤

1. 开始从第二个元素进行遍历：第一个元素默认为已排序序列。
2. 取出当前元素：存储当前元素值，用以之后插入。
3. 比较与移动：将当前元素与已排序数组中的元素从后向前逐一比较。如果已排序的元素大于当前元素，将该元素后移。
4. 插入元素：重复步骤3，直到找到当前元素的正确位置，并将其插入。

性能

• 时间复杂度：最好情况 (O(n))（数组已经是排序好的情况），平均和最坏情况 (O(n^2))，因为需要两层循环。
• 空间复杂度：(O(1))。插入排序是原地排序，不需要额外的存储空间。

示例代码

class Solution:def sortArray(self, nums: List[int]) -> List[int]:n = len(nums)# 遍历除第一个元素外的所有元素for i in range(1, n):temp = nums[i]  # 当前要插入的元素j = i# 将当前元素插入到已排序的部分while j > 0 and nums[j - 1] > temp:nums[j] = nums[j - 1]  # 已排序元素后移j -= 1nums[j] = temp  # 插入当前元素到正确位置return nums

应用场景

插入排序适用于数据量较小，或者数据基本有序的情况。由于其简单性，它通常被用作更复杂算法>排序算法的一部分，例如在快速排序和归并排序中处理小数组。

5.希尔排序

算法思想

希尔排序（Shell Sort）是一种基于插入排序的算法>排序算法，它通过引入“间隔”的概念来改善插入排序的性能。希尔排序也被称为“缩小增量排序”，其基本思想是使数组中任意间隔为 gap 的元素都是有序的，这个 gap 会逐渐减小，最终减至1，整个数组就变为有序了。

算法步骤

1. 选择合适的间隔序列：希尔排序的关键是间隔序列的选择。常用的方法是开始时选取大的间隔，逐步减小，直至1。一种常见的选择是使用数组长度的一半作为起始间隔，然后逐步对间隔取半，直到间隔为1。

2. 按间隔进行排序：对于每个间隔 gap，数组被分为多个子数组，每个子数组包含间隔为 gap 的元素。对每个子数组进行插入排序。

3. 减小间隔：完成当前间隔的排序后，减小间隔值，重复上述排序过程。

4. 最终插入排序：当间隔减至1时，执行一次标准的插入排序，此时数组已经部分有序，因此插入排序会非常高效。

性能

• 时间复杂度：希尔排序的时间复杂度与选取的间隔序列有很大关系，最坏情况可达 (O(n^2))，但通过合理选择间隔，性能可以显著提升。一些更高效的间隔序列，如Hibbard序列，可以达到 (O(n^{3/2})) 的时间复杂度。
• 空间复杂度：希尔排序是原地算法>排序算法，空间复杂度为 (O(1))。

示例代码

下面是希尔排序的Python代码示例：

def shell_sort(nums):n = len(nums)  # 获取数组的长度gap = n // 2   # 初始间隔设置为数组长度的一半# 循环直到间隔为0while gap > 0:# 从gap开始，对每个子数组进行插入排序for i in range(gap, n):temp = nums[i]  # 存储当前位置的元素，待会可能会移动j = i# 执行插入排序，将nums[i]插入到前面的正确位置while j >= gap and nums[j - gap] > temp:  # 如果前面的元素大于当前元素nums[j] = nums[j - gap]  # 将大元素向后移动j -= gap  # 减少索引，继续向前比较nums[j] = temp  # 找到正确位置，将当前元素放置此处gap //= 2  # 缩减间隔值return nums  # 返回排序后的数组

应用场景

希尔排序适合中等大小的数组。它的优点是简单易懂，且不需要额外的内存开销。在数据量不是特别大时，希尔排序通常比其他 (O(n \log n)) 的复杂算法>排序算法如快速排序、归并排序更简单、更快。然而，对于非常大的数据集，选择更现代、更高效的算法可能更好。

6.归并排序

算法思想

归并排序的核心思想是将两个已排序的序列合并成一个序列。整个排序过程主要包括两个操作：分解和合并。

• 分解：将原始数组分解成较小的数组，直到每个小数组只有一个元素或空。
• 合并：逐步将这些小数组合并成较大的数组，保证每次合并后的数组都是有序的。

算法步骤

1. 递归分割：从中间将数组分割成两部分，然后对这两部分分别进行归并排序。
2. 合并：将两个排序好的半部分合并成一个完整的排序数组。
   • 设置两个指针，分别指向两个数组的起始位置。
   • 比较两个指针指向的元素，选择较小的元素放入新数组，移动该指针。
   • 重复上述过程直到一个数组的所有元素都已经被合并。
   • 将另一个数组剩余的元素复制到新数组中。

性能

• 时间复杂度：
  • 最好、平均和最坏情况下的时间复杂度均为 (O(n \log n))，其中 (n) 是数组长度。
• 空间复杂度：
  • 归并排序需要额外的存储空间，空间复杂度为 (O(n))，因为它需要一个大小等于原数组的临时数组来存放合并过程中的中间结果。

示例代码

下面是归并排序的一个Python实现示例：

def merge_sort(nums):if len(nums) <= 1:return nums# 分割点mid = len(nums) // 2# 递归排序左半部left = merge_sort(nums[:mid])# 递归排序右半部right = merge_sort(nums[mid:])# 合并已排序的部分return merge(left, right)def merge(left, right):sorted_list = []i = j = 0# 合并两个排序好的列表while i < len(left) and j < len(right):if left[i] < right[j]:sorted_list.append(left[i])i += 1else:sorted_list.append(right[j])j += 1# 将剩余的元素加入到排序列表中sorted_list.extend(left[i:])sorted_list.extend(right[j:])return sorted_list

应用场景

归并排序特别适合于大数据量的排序，因为它的运行时间仅与数据量的对数乘积有关。它也广泛应用于外部排序中，例如大数据文件的排序，因为这些数据不能同时存放在内存中，需要分批次处理。

7.堆排序

算法思想

堆排序的核心思想是首先将待排序的数组构造成一个最大堆，这样最大的元素就位于堆顶。然后将堆顶元素（即当前最大值）与堆的最后一个元素交换，这样最大元素就位于数组的末尾。随后，缩小堆的大小（排除数组末尾的最大元素），并重新调整剩余数组，使其再次成为最大堆。重复此过程直到所有元素都被排序。

算法步骤

1. 构建最大堆：将无序数组构建成一个最大堆，从最后一个非叶子节点开始，进行下沉调整（调整为最大堆）。
2. 排序：将堆顶元素（最大值）与堆的最后一个元素交换，然后缩减堆的大小，对新的堆顶元素进行下沉调整。重复这个过程，直到堆的大小为1。

性能

• 时间复杂度：
  • 最好、平均和最坏情况下的时间复杂度都是 (O(n \log n))。
• 空间复杂度：
  • 堆排序是一个原地算法>排序算法，空间复杂度为 (O(1))。

示例代码

下面是堆排序的Python实现示例：

class Solution:def sortArray(self, nums: List[int]) -> List[int]:def heapify(nums, n, i):# 初始化 largest 为当前节点largest = i# 左子节点的索引left = 2 * i + 1# 右子节点的索引right = 2 * i + 2# 检查左子节点是否存在且是否大于当前节点if left < n and nums[left] > nums[largest]:largest = left# 检查右子节点是否存在且是否大于当前节点if right < n and nums[right] > nums[largest]:largest = right# 如果当前节点不是最大节点，则与最大节点交换if largest != i:nums[i], nums[largest] = nums[largest], nums[i]# 递归调整交换后的子树heapify(nums, n, largest)n = len(nums)# 构建最大堆# 从最后一个非叶子节点开始向上构建最大堆for i in range(n // 2 - 1, -1, -1):heapify(nums, n, i)# 提取元素# 从堆中依次取出元素并调整堆结构for i in range(n - 1, 0, -1):# 将堆顶元素（最大）与当前末尾元素交换，将最大元素固定到其最终位置nums[i], nums[0] = nums[0], nums[i]# 缩小堆大小并重新调整为最大堆heapify(nums, i, 0)return nums

应用场景

堆排序特别适用于那些关心极值的场景，例如求解最大或最小的几个元素。由于其稳定的 (O(n \log n)) 性能和原地排序的特性，堆排序非常适合处理大数据量的场景。不过，由于在实际的排序过程中，堆排序的常数项较大，且缓存局部性较差，通常它的表现不如快速排序和归并排序。

8.计数排序

计数排序（Counting Sort）是一种非比较的算法>排序算法，特别适用于那些数值范围（或键的范围）不是很大的情况。它通过计算每个元素的出现次数来确定每个元素的排序位置。

算法思想

计数排序的核心思想是将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 counts 的第 i-min 项；
3. 对所有的计数累加（从 counts 中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素 i 放在新数组的第 counts[i-min] 项，每放一个元素就将 counts[i-min] 减去1。

性能

• 时间复杂度：计数排序的时间复杂度为 (O(n+k))，其中 (n) 是数组长度，(k) 是数组中数据的范围。
• 空间复杂度：因为需要额外开辟一个数组来存储频率信息，所以空间复杂度为 (O(k))。

示例代码

下面是计数排序的一个Python示例实现：

def counting_sort(nums):if not nums:return nums# Step 1: 获取数列的最大最小值max_val, min_val = max(nums), min(nums)size = max_val - min_val + 1# Step 2: 创建计数数组，并统计对应元素的个数counts = [0] * sizefor num in nums:counts[num - min_val] += 1# Step 3: 累加前面的计数，修改计数数组for i in range(1, size):counts[i] += counts[i - 1]# Step 4: 反向填充目标数组sorted_nums = [0] * len(nums)for num in reversed(nums):sorted_nums[counts[num - min_val] - 1] = numcounts[num - min_val] -= 1return sorted_nums

应用场景

计数排序不是比较排序，排序的速度快于任何比较算法>排序算法。由于其 (O(n+k)) 的时间复杂度，计数排序适用于当 (k) （即数据范围）不是很大并且数据量比较大的情况。

注意事项

• 计数排序只适用于数据范围不大的情况，因为数据范围越大，所需的额外存储空间也越大。
• 计数排序是稳定的算法>排序算法。
• 计数排序对输入数据有较强依赖性，适合于数据范围小且数据分布均匀的情况。

9.桶排序

桶排序（Bucket Sort）是一种分布式的算法>排序算法，通过将数据分散到多个有序的桶中，对每个桶内的数据进行排序，最后将各个桶的数据顺序合并，从而实现整个数组的排序。这种方法在特定条件下效率极高，尤其适用于数据均匀分布的场景。

算法思想

桶排序的基本思想是将范围较大的数据分散到多个称为“桶”的子区间里，这样每个桶包含的数据项就相对较少。每个桶内的数据单独排序，可以采用不同的算法>排序算法，或递归地使用桶排序。最后，将各个桶中的数据有序合并起来，以得到完整的排序数组。

算法步骤

1. 确定桶的数量和范围：根据原始数据的范围和桶的设计策略确定桶的数量。
2. 初始化桶：创建一系列空桶，用来存放数据。
3. 分配数据到桶中：遍历原始数据，根据数据值分配到对应的桶中。
4. 对每个桶内数据进行排序：可以使用任意算法>排序算法，通常选择快速排序或插入排序。
5. 合并桶中的数据：按顺序从每个桶中收集数据，合并成一个完整的有序数组。

性能

• 时间复杂度：最好情况为 (O(n+k))，其中 (n) 是元素数量，(k) 是桶的数量；最坏情况为 (O(n^2))，当所有元素都分布在一个桶中时；平均情况通常接近 (O(n))，特别是当元素均匀分布时。
• 空间复杂度：(O(n+k))，其中 (n) 是元素数量，(k) 是桶的数量，需要额外的空间存放桶中的元素。

示例代码

def bucket_sort(nums):if not nums:return nums# 1. 初始化桶max_val, min_val = max(nums), min(nums)bucket_size = (max_val - min_val) / len(nums) + 1buckets = [[] for _ in range(int((max_val - min_val) / bucket_size) + 1)]# 2. 分配数据到桶中for num in nums:idx = int((num - min_val) / bucket_size)buckets[idx].append(num)# 3. 对每个桶进行排序for bucket in buckets:bucket.sort()# 4. 合并数据sorted_nums = []for bucket in buckets:sorted_nums.extend(bucket)return sorted_nums

3.排序可以应用多种方法，如插入排序，对应代码如下：

class Solution:def sortArray(self, nums: List[int]) -> List[int]:def insert_sort(nums):# 插入排序for i in range(1, len(nums)):temp = nums[i]j = iwhile j > 0 and nums[j-1] > temp:nums[j] = nums[j-1]j -= 1nums[j] = tempreturn nums# 桶排序# 桶的数量，可以根据实际情况调整num_buckets = 5# 最大值和最小值max_val, min_val = max(nums), min(nums)# 桶的大小bucket_size = (max_val - min_val) / num_buckets + 1# 创建桶数组buckets = [[] for _ in range(num_buckets)]# 分配数组元素到桶中for num in nums:# 计算当前元素应该放在哪个桶中index = int((num - min_val) // bucket_size)buckets[index].append(num)# 对每个桶进行排序，这里使用插入排序for bucket in buckets:insert_sort(bucket)# 合并桶中的元素sorted_nums = []for bucket in buckets:sorted_nums.extend(bucket)return sorted_nums

应用场景

桶排序特别适用于：

• 处理大量数据，且数据分布均匀时。
• 需要稳定排序时，例如需要保持相同元素之间的相对顺序。
• 外部排序，当内存不足以同时处理所有数据时，可以将数据分布到多个桶中分别处理。

10.基数排序

基数排序（Radix Sort）是一种非比较型整数算法>排序算法，其通过分配和收集过程来排序数据。它的工作原理是按照数字的每一位进行排序，通常从最低位开始，最后一次是最高位。基数排序对于整数或可以分解成整数键值的其他类型数据（如日期和时间戳）效果很好。

算法思想

基数排序的核心思想是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

算法步骤

1. 确定排序的轮数：根据数组中最大数的位数决定，位数最多的数有多少位，就需要进行多少轮排序。
2. 每一轮排序过程：
   • 根据当前位（个位、十位、百位…）来分配桶。例如在处理个位数时，将数据放入0-9号桶中。
   • 将所有桶中的数据按顺序收集起来。
3. 重复以上过程：对于每一位执行步骤2，直到最高位。

性能

• 时间复杂度：基数排序的时间复杂度是 (O(nk))，其中 (n) 是数组长度，(k) 是数字的最大位数。
• 空间复杂度：由于需要额外的空间来存放桶，基数排序的空间复杂度是 (O(n+k))。

示例代码

class Solution:def sortArray(self, nums: List[int]) -> List[int]:if not nums:return nums# 找到最大数，确定最大位数max_num = max(nums)max_digit = len(str(max_num))# 从个位开始，对每一位进行排序处理bucket, digit = [[] for i in range(10)], 1while max_digit > 0:for num in nums:# 计算每个数当前位的数字radix = num // digit % 10bucket[radix].append(num)# 按当前位数收集数据idx = 0for b in bucket:for num in b:nums[idx] = numidx += 1b.clear()# 移动到下一位digit *= 10max_digit -= 1return nums

应用场景

基数排序非常适合用于：

• 数据范围较大但位数较少的排序场景，如手机号码排序、长整数排序等。
• 需要稳定排序的场合，基数排序保证相同元素的相对位置不变。

参考：
1.https://zhuanlan.zhihu.com/p/672510864
2.https://datawhalechina.github.io/leetcode-notes/#/keys/ch06-keys/06.01.02-Exercises-Key