一、基于比较的排序算法
基于比较的排序算法通过比较元素之间的大小来完成排序。
1.1 冒泡排序（Bubble Sort）
特点：通过多次交换相邻元素，将最大（或最小）元素“冒泡”到序列末端。
时间复杂度：
- 最好：O(n)（输入数组已排序）
- 最坏：O(n²)
空间复杂度：O(1)（原地排序）
稳定性：稳定
适用场景：适合小规模、几乎有序的数据集。
实现代码（Python）：
def bubble_sort(arr):n = len(arr)for i in range(n):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
1.2 选择排序（Selection Sort）
特点：每次从未排序部分选择最小元素，放到已排序部分末尾。
时间复杂度：
- 最好/最坏：O(n²)
空间复杂度：O(1)
稳定性：不稳定
适用场景：适合数据量小、对稳定性无要求的场景。
实现代码：
def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr
1.3 插入排序（Insertion Sort）
特点：将序列分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的合适位置。
时间复杂度：
- 最好：O(n)（输入数组已排序）
- 最坏：O(n²)
空间复杂度：O(1)
稳定性：稳定
适用场景：适合小规模或几乎有序的数据集。
实现代码：
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr
1.4 快速排序（Quick Sort）
特点：基于分治思想，通过选择一个“基准”（pivot），将数组划分为两部分，递归排序。
时间复杂度：
- 最好：O(n log n)
- 最坏：O(n²)（输入数组完全逆序，或基准选择不当）
- 平均：O(n log n)
空间复杂度：O(log n)（递归栈空间）
稳定性：不稳定
适用场景：适合大规模数据，基准选取合理时效率极高。
实现代码：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)
1.5 归并排序（Merge Sort）
特点：基于分治思想，将数组递归分成两半，排序后再合并。
时间复杂度：
- 最好/最坏/平均：O(n log n)
空间复杂度：O(n)
稳定性：稳定
适用场景：适合需要稳定排序的大规模数据。
实现代码：
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result
1.6 堆排序（Heap Sort）
特点：利用堆数据结构的性质进行排序。
时间复杂度：
- 最好/最坏/平均：O(n log n)
空间复杂度：O(1)
稳定性：不稳定
适用场景：适合需要原地排序的大规模数据。
实现代码：
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)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[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr
二、非基于比较的排序算法
非基于比较的排序算法利用数据的特定性质排序，时间复杂度低于 O(n log n)。
2.1 计数排序（Counting Sort）
特点：通过统计每个元素出现的次数进行排序。
时间复杂度：O(n + k)（k 为数据范围）
空间复杂度：O(n + k)
稳定性：稳定
适用场景：适合数据范围较小的整数排序。
实现代码（Python）：
def counting_sort(arr):if len(arr) == 0:return arr# 获取数组中的最大值和最小值max_val = max(arr)min_val = min(arr)# 创建计数数组，计数范围是最大值和最小值之间的数字range_of_elements = max_val - min_val + 1count = [0] * range_of_elementsoutput = [0] * len(arr)# 统计每个元素的出现次数for num in arr:count[num - min_val] += 1# 计算累加计数for i in range(1, len(count)):count[i] += count[i - 1]# 从后往前填充输出数组，保证稳定性for num in reversed(arr):output[count[num - min_val] - 1] = numcount[num - min_val] -= 1return output
2.2 基数排序（Radix Sort）
特点：按位数进行排序，从低位到高位依次排列。
时间复杂度：O(d*(n+k))（d 为位数，k 为基数范围）
空间复杂度：O(n+k)
稳定性：稳定
适用场景：适合对固定范围内的整数进行排序。
实现代码（Python）：
def counting_sort_radix(arr, exp):n = len(arr)output = [0] * n # 输出数组count = [0] * 10 # 假设数字为0-9# 存储当前位数的计数for i in range(n):index = arr[i] // expcount[index % 10] += 1# 累加计数数组for i in range(1, 10):count[i] += count[i - 1]# 构建输出数组i = n - 1while i >= 0:index = arr[i] // expoutput[count[index % 10] - 1] = arr[i]count[index % 10] -= 1i -= 1# 拷贝输出数组到原数组for i in range(n):arr[i] = output[i]def radix_sort(arr):# 获取最大元素max_val = max(arr)# 从最低位开始进行排序exp = 1while max_val // exp > 0:counting_sort_radix(arr, exp)exp *= 10return arr
2.3 桶排序（Bucket Sort）
特点：将数据分散到若干桶中，各桶内分别排序，然后合并结果。
时间复杂度：O(n)（理想情况下）
空间复杂度：O(n)
稳定性：稳定（视桶内排序算法而定）
适用场景：适合数据分布均匀的情况。
实现代码（Python）：
def bucket_sort(arr):if len(arr) == 0:return arr# 找到数组中的最大值和最小值min_val = min(arr)max_val = max(arr)# 计算桶的数量bucket_count = len(arr)bucket_range = (max_val - min_val) / bucket_count# 创建桶buckets = [[] for _ in range(bucket_count)]# 将元素分配到桶中for num in arr:index = int((num - min_val) // bucket_range)if index == bucket_count:index -= 1buckets[index].append(num)# 对每个桶中的元素进行排序for i in range(bucket_count):buckets[i] = sorted(buckets[i])# 合并所有桶中的元素sorted_arr = []for bucket in buckets:sorted_arr.extend(bucket)return sorted_arr
总结
| 算法 | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(1) | 稳定 | 小规模或近似有序 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 无需稳定性的简单场景 |
| 插入排序 | O(n²) | O(n) | O(1) | 稳定 | 小规模或近似有序 |
| 快速排序 | O(n²) | O(n log n) | O(log n) | 不稳定 | 大规模一般场景 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模需要稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 原地排序需求 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 稳定 | 小范围整数 |
| 基数排序 | O(d * (n + k)) | O(d * (n + k)) | O(n+k) | 稳定 | 适合对固定范围内的整数进行排序 |
| 桶排序 | O(n²) | O(n + k) | O(n) | 稳定 | 适合数据分布均匀的情况 |
