前言
近期在准备下半年的软考，在刷题过程中遇到了一些经典的数据结构与算法的经典例题，在这里我以博客的形式回顾记录下【排序算法】的应用以及相关拓展。
概述
常见10种的排序算法包括：【冒泡排序】、【插入排序】、【选择排序】、【快速排序】、归并排序】、【堆排序】、【希尔排序】【计数排序】、【桶排序】、【 基数排序】。在这里我们使用python语言来实现这些排序算法，简化下实现流程，我们生成一个长度为10的随机数组：
python
复制代码
import random # 生成一个长度为10，元素在0-100之间的随机数组 arr = [random.randint(0, 100) for _ in range(10)] print(arr)
冒泡排序
冒泡排序是一种简单的排序算法，它的原理是通过不断交换相邻元素的位置，将最大的元素逐渐“冒泡”到序列的末尾，从而实现排序。
具体实现步骤如下：
- 首先，比较相邻的两个元素，如果前面的元素比后面的元素大，则交换它们的位置。
- 对每一对相邻的元素都进行上述比较和交换，这样一轮下来，最大的元素就会“冒泡”到序列的末尾。
- 针对剩余未排序的元素，重复第 1 步和第 2 步，直到整个序列都被排序。
在实现过程中，需要使用两层循环来实现冒泡排序。外层循环控制排序轮数，内层循环控制每轮比较的次数。具体实现步骤如下：
- 首先，外层循环从第一个元素开始，依次遍历到倒数第二个元素。
- 内层循环从第一个元素开始，依次遍历到倒数第二个未排序的元素。
- 在内层循环中，比较相邻的两个元素，如果前面的元素比后面的元素大，则交换它们的位置。
- 每轮内层循环结束后，最大的元素就会被“冒泡”到末尾，因此外层循环可以减少一次遍历。
- 最终，整个序列就被排好序了。
冒泡排序的时间复杂度为 O(n^2)，空间复杂度为O(1)。，因此它不适合用于大规模数据的排序。
ini
复制代码
# 冒泡 def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # 最后i个元素已经排好序，不需要再比较 for j in range(0, n-i-1): # 如果当前元素大于下一个元素，则交换它们 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
插入排序
插入排序是一种简单的排序算法，其基本原理是将未排序的元素一个一个插入到已排序的序列中，直到所有元素都被排序。
插入排序的实现步骤如下：
- 将序列的第一个元素视为已排序的序列。
- 从第二个元素开始，依次将每个元素插入到已排序的序列中。具体操作是将该元素与已排序序列中的元素从后往前比较，如果该元素比已排序序列中的元素小，则将已排序序列中的元素往后移动一个位置，直到找到该元素应该插入的位置。
- 重复步骤2，直到所有元素都被插入到已排序序列中。
实现过程中，可以使用嵌套循环来完成插入排序。外层循环从第二个元素开始遍历，内层循环从当前元素往前遍历已排序序列，直到找到该元素应该插入的位置。在内层循环中，如果已排序序列中的元素比当前元素大，则将其往后移动一个位置。最后，将当前元素插入到找到的位置。
ini
复制代码
# 插入排序 def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr
插入排序的时间复杂度为O(n²)，空间复杂度为O(1)。虽然插入排序的时间复杂度不如快速排序和归并排序等算法，但是对于小规模数据的排序，插入排序的效率比较高。
选择排序
选择排序是一种简单的排序算法，其基本原理是每次选择未排序序列中的最小元素，将其放到已排序序列的末尾，直到所有元素都被排序。
选择排序的实现步骤如下：
- 将序列的第一个元素视为已排序的序列。
- 从第二个元素开始，依次遍历未排序的序列，找到其中最小的元素，将其放到已排序序列的末尾。
- 重复步骤2，直到所有元素都被排序。
实现过程中，可以使用嵌套循环来完成选择排序。外层循环从第一个元素开始遍历，内层循环从当前元素的下一个元素开始遍历未排序的序列，找到其中最小的元素，并将其与当前元素交换位置。
选择排序的时间复杂度为O(n²)，空间复杂度为O(1)。虽然选择排序的时间复杂度不如快速排序和归并排序等算法，但是对于小规模数据的排序，选择排序的效率比较高。
ini
复制代码
# 选择排序 def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr
快速排序
快速排序是一种常用的排序算法，其原理是通过选择一个基准元素，将序列分成两个子序列，将比基准元素小的元素放到左边，比基准元素大的元素放到右边，然后对左右两个子序列递归地进行快速排序，最终得到一个有序序列。
快速排序的实现步骤如下：
- 选择一个基准元素，通常选择序列的第一个元素。
- 将序列分成两个子序列，一个子序列包含比基准元素小的元素，一个子序列包含比基准元素大的元素。
- 对左右两个子序列递归地进行快速排序。
- 将左子序列、基准元素、右子序列依次连接起来，得到一个有序序列。
ini
复制代码
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right)
归并排序
归并排序是一种基于分治思想的排序算法，它将待排序的序列分成两个子序列，对每个子序列递归地进行排序，然后将两个有序子序列合并成一个有序序列。
其实现步骤如下：
- 分解：将待排序的序列分成两个子序列，递归地将每个子序列分解成更小的子序列，直到每个子序列只有一个元素为止。
- 合并：将两个有序子序列合并成一个有序序列。具体地，可以使用两个指针分别指向两个子序列的头部，比较两个指针所指向的元素的大小，将较小的元素放入结果序列中，并将该指针后移一位，直到其中一个子序列已经全部放入结果序列中，然后将另一个子序列中剩余的元素依次放入结果序列中。
- 返回：将合并后的有序序列作为结果返回。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，是一种稳定的排序算法。
ini
复制代码
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left_arr = arr[:mid] right_arr = arr[mid:] left_arr = merge_sort(left_arr) right_arr = merge_sort(right_arr) return merge(left_arr, right_arr) def merge(left_arr, right_arr): result = [] i, j = 0, 0 while i < len(left_arr) and j < len(right_arr): if left_arr[i] <= right_arr[j]: result.append(left_arr[i]) i += 1 else: result.append(right_arr[j]) j += 1 result += left_arr[i:] result += right_arr[j:] return result
堆排序
堆排序是一种基于堆的排序算法，它将待排序的序列构建成一个堆，然后依次取出堆顶元素，将其放到已排序序列的末尾。
其实现步骤如下：
- 构建堆：将待排序的序列构建成一个堆。具体地，可以先将序列看成一棵完全二叉树，然后从最后一个非叶子节点开始，依次将每个节点与其子节点比较，如果节点的值比其子节点的值小，则交换这两个节点的值，然后继续向下比较，直到该节点没有子节点或者节点的值已经比其子节点的值大。
- 排序：依次取出堆顶元素，将其放到已排序序列的末尾。具体地，可以将堆顶元素与堆底元素交换，然后将堆的大小减1，然后从堆顶开始向下调整堆，以保持堆的性质。
- 重复：重复步骤2，直到堆中只剩下一个元素为止。
堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种不稳定的排序算法。
ini
复制代码
# 堆排序 def heap_sort(arr): n = len(arr) # 构建最大堆 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 依次取出堆顶元素，将其放到已排序序列的末尾 for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr def heapify(arr, n, i): # 在以i为根节点的子树中构建最大堆 largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
希尔排序
希尔排序，也称递减增量排序，是插入排序的一种改进版本。希尔排序的基本思想是将待排序的序列分成若干个子序列，对每个子序列进行插入排序，然后逐渐缩小子序列的长度，最终进行一次插入排序，完成排序。
实现步骤如下：
- 选择一个增量序列，例如：N/2，N/4，N/8...直到增量为1。
- 对于每个增量，将待排序的序列分成若干个子序列，每个子序列的元素下标之间相差增量。
- 对每个子序列进行插入排序。
- 逐渐缩小增量，重复步骤2和3，直到增量为1。
- 最后进行一次插入排序，完成排序。
希尔排序的时间复杂度取决于增量序列的选择，通常情况下，时间复杂度为O(n^2)。希尔排序是一种不稳定的排序算法，因为它会改变相等元素的原始顺序。
ini
复制代码
def shell_sort(arr): n = len(arr) gap = n // 2 while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap //= 2 return arr
计数排序
计数排序是一种非比较排序算法，其基本思想是统计每个元素在序列中出现的次数，然后根据元素出现的次数将元素排序。计数排序的时间复杂度为 O(n+k)，其中 n 是序列的长度，k 是序列中元素的取值范围。
计数排序的实现步骤如下：
- 找出序列中的最大值和最小值，确定计数数组的长度。
- 统计每个元素在序列中出现的次数，将其存储在计数数组中。
- 计算每个元素在有序序列中的位置，即前缀和数组。
- 从后往前遍历原序列，根据前缀和数组将元素放到有序序列中的对应位置。
ini
复制代码
def countingSort(arr): # 找到数组中的最大值 max_value = max(arr) # 初始化计数数组 count = [0] * (max_value + 1) # 统计每个元素出现的次数 for i in arr: count[i] += 1 # 根据计数数组排序 sorted_arr = [] for i in range(max_value + 1): sorted_arr.extend([i] * count[i]) return sorted_arr
桶排序
桶排序是一种非比较排序算法，它的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，最后将每个桶中的数据按照顺序依次取出，即可得到排序结果。桶排序的时间复杂度为O(n)，但需要额外的空间来存储桶。
桶排序的实现步骤如下：
- 找到待排序序列中的最大值和最小值。
- 计算出桶的个数，并创建相应个数的桶。
- 遍历待排序序列，将每个元素分配到对应的桶中。
- 对每个桶中的元素进行排序，可以使用任意排序算法，如插入排序等。
- 将每个桶中的元素按照顺序依次取出，即可得到排序结果。
桶排序的优化：
- 如果待排序序列中的元素分布不均匀，则可以使用动态桶的方式，即根据待排序数据的分布情况动态的调整桶的个数和桶的大小。
- 如果待排序序列中的元素重复度较高，则可以使用计数排序的方式，即对每个桶中的元素进行计数，避免重复元素的排序。
- 如果待排序序列中的元素不是整数类型，可以考虑使用基数排序的方式，即按照元素的位数从低到高进行排序。
桶排序的适用场景：
桶排序适用于待排序序列中的元素分布均匀、元素重复度低、元素取值范围不大等情况。例如，对学生的成绩进行排序，成绩的取值范围通常是0到100，且分布比较均匀，这时候可以使用桶排序来进行排序。
ini
复制代码
def bucket_sort(arr, bucket_size=5): if len(arr) == 0: return arr # 确定桶的个数 min_val, max_val = min(arr), max(arr) bucket_count = (max_val - min_val) // bucket_size + 1 buckets = [[] for _ in range(bucket_count)] # 将元素放入桶中 for i in range(len(arr)): bucket_index = (arr[i] - min_val) // bucket_size buckets[bucket_index].append(arr[i]) # 对每个桶进行排序 for i in range(bucket_count): buckets[i].sort() # 将桶中的元素按顺序合并 sorted_arr = [] for bucket in buckets: sorted_arr += bucket return sorted_arr
基数排序
基数排序是一种非比较排序算法，它的原理是将待排序的数字按照位数从低到高进行排序。
具体的实现步骤如下：
- 找出待排序数列中最大的数字，并确定其位数。
- 根据位数从低到高的顺序，依次对数列进行排序。
- 对于每一位数，将待排序数列中的数字按照该位数进行分桶。例如，对于个位数，将所有数字按照个位数的大小分为10个桶。
- 将分好的桶按照顺序合并成一个新的数列。
- 重复第3步和第4步，直到所有位数都处理完毕。
- 最后得到的数列即为排好序的结果。
基数排序的时间复杂度为O(d * (n + k))，其中d是数字的位数，n是待排序数列的长度，k是数字的取值范围。由于基数排序需要使用桶来存储数字，因此它需要额外的空间来存储桶，空间复杂度为O(n + k)。
基数排序的优点是稳定性好，适用于数字比较小但位数比较多的数列。但是它的缺点是需要额外的空间来存储桶，当数字的取值范围较大时，空间消耗会很大。
ini
复制代码
# 基数排序 def radix_sort(arr): # 获取数组中的最大值 max_num = max(arr) # 获取最大值的位数 digit = len(str(max_num)) # 初始化桶 bucket = [[] for _ in range(10)] # 进行 digit 次排序 for i in range(digit): # 将每个元素放入对应的桶中 for num in arr: index = (num // (10 ** i)) % 10 bucket[index].append(num) # 将桶中的元素按顺序放回数组中 arr.clear() for j in range(10): arr.extend(bucket[j]) bucket[j].clear() return arr
复杂度
在软考中常见出现时间复杂度以及空间复杂度，这里先带大家回顾下这两个复杂度的概念：
时间复杂度和空间复杂度都是用于【衡量算法效率】的指标。
【时间复杂度】 是指算法运行所需要的时间，通常用大 O 表示法来表示。大 O 表示法是一种用于描述算法时间复杂度的符号表示法，它表示算法运行时间的增长率和输入数据规模 n 的关系。例如，如果一个算法的时间复杂度为 O(n)，则算法的运行时间随着输入数据规模 n 的增加而线性增长。
【空间复杂度】是指算法运行所需要的空间，通常用大 O 表示法来表示。空间复杂度是指算法在运行过程中所需要的额外空间，不包括输入数据所占用的空间。例如，如果一个算法的空间复杂度为 O(n)，则算法在运行过程中所需要的额外空间随着输入数据规模 n 的增加而线性增长。
排序算法中的时间复杂度和空间复杂度：
结尾
不知不觉中写了这么多，软考备考路漫漫，仅以此篇分享众朋客飨阅！若有误烦请评论告知，感谢！
