LeetCode 排序算法的比较与选择题解

LeetCode 排序算法的比较与选择题解题目描述比较各种排序算法的时间复杂度、空间复杂度、稳定性等特性并根据不同的场景选择合适的排序算法。示例对于小规模数据选择插入排序对于大规模数据选择快速排序或归并排序对于元素范围较小的数据选择计数排序。解题思路方法排序算法的比较与选择思路不同的排序算法有不同的时间复杂度、空间复杂度和稳定性适用于不同的场景。选择排序算法时需要考虑以下因素数据规模小规模数据适合使用插入排序、冒泡排序等简单排序算法大规模数据适合使用快速排序、归并排序、堆排序等高效排序算法。数据分布如果数据基本有序插入排序的效率会很高如果数据分布均匀桶排序的效率会很高。数据范围如果数据范围较小计数排序的效率会很高如果数据范围较大基数排序的效率会很高。稳定性要求如果需要保持相同元素的相对顺序需要选择稳定的排序算法如插入排序、归并排序等。复杂度分析各种排序算法的时间复杂度、空间复杂度和稳定性如下表所示排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(n)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(n)O(1)稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定桶排序O(n k)O(n²)O(n)O(n k)稳定基数排序O(n * k)O(n * k)O(n * k)O(n k)稳定代码实现方法根据场景选择排序算法# 根据场景选择排序算法 def select_sort_algorithm(arr, scenario): 根据场景选择合适的排序算法 参数 arr: 待排序的数组 scenario: 场景描述可选值 - small: 小规模数据 - large: 大规模数据 - nearly_sorted: 基本有序的数据 - small_range: 元素范围较小的数据 - uniform_distribution: 均匀分布的数据 返回 排序后的数组 n len(arr) if scenario small: # 小规模数据选择插入排序 return insertion_sort(arr.copy()) elif scenario large: # 大规模数据选择快速排序 return quick_sort(arr.copy()) elif scenario nearly_sorted: # 基本有序的数据选择插入排序 return insertion_sort(arr.copy()) elif scenario small_range: # 元素范围较小的数据选择计数排序 return counting_sort(arr.copy()) elif scenario uniform_distribution: # 均匀分布的数据选择桶排序 return bucket_sort(arr.copy()) else: # 默认选择快速排序 return quick_sort(arr.copy()) # 插入排序 def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and key arr[j]: arr[j 1] arr[j] j - 1 arr[j 1] key return arr # 快速排序 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) # 计数排序 def counting_sort(arr): if not arr: return arr min_val min(arr) max_val max(arr) count_len max_val - min_val 1 count [0] * count_len for num in arr: count[num - min_val] 1 sorted_arr [] for i in range(count_len): sorted_arr.extend([i min_val] * count[i]) return sorted_arr # 桶排序 def bucket_sort(arr): if not arr: return arr bucket_count 10 min_val min(arr) max_val max(arr) bucket_range (max_val - min_val 1) / bucket_count buckets [[] for _ in range(bucket_count)] for num in arr: bucket_index int((num - min_val) / bucket_range) bucket_index min(bucket_index, bucket_count - 1) buckets[bucket_index].append(num) for i in range(bucket_count): buckets[i].sort() sorted_arr [] for bucket in buckets: sorted_arr.extend(bucket) return sorted_arr # 测试 def test_select_sort_algorithm(): arr [64, 34, 25, 12, 22, 11, 90] print(小规模数据:, select_sort_algorithm(arr, small)) print(大规模数据:, select_sort_algorithm(arr, large)) print(基本有序的数据:, select_sort_algorithm(arr, nearly_sorted)) print(元素范围较小的数据:, select_sort_algorithm(arr, small_range)) print(均匀分布的数据:, select_sort_algorithm(arr, uniform_distribution)) if __name__ __main__: test_select_sort_algorithm()测试用例测试用例根据场景选择排序算法输入[64, 34, 25, 12, 22, 11, 90]输出小规模数据: [11, 12, 22, 25, 34, 64, 90] 大规模数据: [11, 12, 22, 25, 34, 64, 90] 基本有序的数据: [11, 12, 22, 25, 34, 64, 90] 元素范围较小的数据: [11, 12, 22, 25, 34, 64, 90] 均匀分布的数据: [11, 12, 22, 25, 34, 64, 90]总结排序算法是计算机科学中的基础算法不同的排序算法有不同的时间复杂度、空间复杂度和稳定性适用于不同的场景。选择合适的排序算法可以提高程序的效率。在选择排序算法时需要考虑以下因素数据规模小规模数据适合使用插入排序、冒泡排序等简单排序算法大规模数据适合使用快速排序、归并排序、堆排序等高效排序算法。数据分布如果数据基本有序插入排序的效率会很高如果数据分布均匀桶排序的效率会很高。数据范围如果数据范围较小计数排序的效率会很高如果数据范围较大基数排序的效率会很高。稳定性要求如果需要保持相同元素的相对顺序需要选择稳定的排序算法如插入排序、归并排序等。掌握各种排序算法的特性和适用场景对于解决实际问题非常重要。