### Python 排序算法的面试题及解法 在 Python 面试中，排序算法是一个常见的考点。以下是一些经典的排序算法问题及其解法，涵盖了从基础到进阶的内容。 #### 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，通过重复遍历列表并比较相邻元素来实现排序。 ```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 ``` 这种方法的时间复杂度为 O(n²)，适合用于小规模数据排序[^1]。 #### 2. 快速排序（Quick Sort） 快速排序是一种高效的排序算法，采用分治策略递归地将数组分成较小的部分进行排序。 ```python 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(n log n)，但在最坏情况下可能达到 O(n²)[^1]。 #### 3. 归并排序（Merge Sort） 归并排序也是一种基于分治策略的排序算法，通过将数组分成两半分别排序后再合并。 ```python def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left_half = merge_sort(arr[:mid]) right_half = merge_sort(arr[mid:]) return merge(left_half, right_half) def merge(left, right): sorted_arr = [] while left and right: if left[0] < right[0]: sorted_arr.append(left.pop(0)) else: sorted_arr.append(right.pop(0)) sorted_arr.extend(left or right) return sorted_arr ``` 归并排序的时间复杂度始终为 O(n log n)，但需要额外的存储空间[^1]。 #### 4. 堆排序（Heap Sort） 堆排序利用二叉堆结构实现排序，首先将数组构建成最大堆或最小堆，然后依次取出堆顶元素。 ```python def heapify(arr, n, 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) 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)，且不需要额外的存储空间[^1]。 #### 5. 计数排序（Counting Sort） 计数排序适用于一定范围内的整数排序，通过统计每个值的出现次数来完成排序。 ```python def counting_sort(arr): max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 sorted_arr = [] for i, cnt in enumerate(count): sorted_arr.extend([i] * cnt) return sorted_arr ``` 计数排序的时间复杂度为 O(n + k)，其中 k 是输入数据的范围大小。 #### 6. 桶排序（Bucket Sort） 桶排序将数据分布到多个桶中，然后对每个桶中的数据进行排序。 ```python def bucket_sort(arr): from math import floor num_buckets = len(arr) buckets = [[] for _ in range(num_buckets)] for num in arr: index = floor(num * num_buckets) buckets[index].append(num) sorted_arr = [] for bucket in buckets: sorted_arr.extend(sorted(bucket)) return sorted_arr ``` 桶排序的时间复杂度取决于桶内排序算法的选择，通常为 O(n)[^1]。 ### 总结 上述排序算法各有优缺点，在面试中可以根据具体场景选择合适的算法。例如，对于大规模数据排序，推荐使用快速排序或归并排序；而对于整数排序，可以考虑计数排序或桶排序。