茂名市网站建设_网站建设公司_Bootstrap_seo优化

一、快速排序（Quick Sort）

1.1 算法原理

快速排序采用分治策略，核心思想是选择一个基准元素，将数组分为两部分，使得左侧所有元素都小于等于基准，右侧所有元素都大于等于基准，然后递归地对左右两部分进行排序。

具体步骤：

1. 选择基准值（pivot）

2. 分区操作：将数组重新排列，所有小于基准的元素放在前面，大于基准的放在后面

3. 递归地对左右两个子数组进行快速排序

1.2 时间复杂度分析

• 最好情况：每次分区都能将数组均匀分成两部分，递归深度为O(log n)，每层比较O(n)次，时间复杂度为O(n log n)

• 平均情况：O(n log n)

• 最坏情况：每次选择的基准都是最大或最小值，导致分区极度不平衡，时间复杂度为O(n²)

• 空间复杂度：O(log n)（递归调用栈）

1.3 快速排序实现

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) def quick_sort_in_place(arr, low=0, high=None): """原地快速排序（节省空间）""" if high is None: high = len(arr) - 1 if low < high: # 分区操作，返回基准位置 pivot_index = partition(arr, low, high) # 递归排序左右两部分 quick_sort_in_place(arr, low, pivot_index - 1) quick_sort_in_place(arr, pivot_index + 1, high) return arr def partition(arr, low, high): """分区函数""" # 选择基准值（这里选择最后一个元素） pivot = arr[high] # i指向小于基准的区域边界 i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] # 将基准值放到正确位置 arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 # 优化版本：三路快排（处理大量重复元素） def quick_sort_3way(arr, low=0, high=None): """三路快速排序，适用于有大量重复元素的数组""" if high is None: high = len(arr) - 1 if low >= high: return # 随机选择基准（避免最坏情况） import random rand_index = random.randint(low, high) arr[low], arr[rand_index] = arr[rand_index], arr[low] pivot = arr[low] # 三路分区：小于、等于、大于基准 lt = low # 小于基准的边界 gt = high # 大于基准的边界 i = low + 1 # 当前元素 while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[gt], arr[i] = arr[i], arr[gt] gt -= 1 else: i += 1 # 递归排序小于和大于部分 quick_sort_3way(arr, low, lt - 1) quick_sort_3way(arr, gt + 1, high) return arr

二、洗牌算法（Shuffle Algorithm）

2.1 算法原理

洗牌算法（Fisher-Yates Shuffle）是一种公平的随机排列算法，保证每个排列出现的概率相等。

核心思想：从最后一个元素开始，随机选择当前位置及之前的某个位置进行交换，然后向前移动。

2.2 时间复杂度与空间复杂度

• 时间复杂度：O(n)

• 空间复杂度：O(1)（原地洗牌）

2.3 洗牌算法实现

python

import random class ShuffleArray: """LeetCode 384. 打乱数组""" def __init__(self, nums): self.original = nums[:] # 保存原始数组 self.array = nums[:] # 当前数组 def reset(self): """重置数组到初始状态""" self.array = self.original[:] return self.array def shuffle(self): """洗牌算法""" # Fisher-Yates 洗牌算法 for i in range(len(self.array) - 1, 0, -1): # 随机选择0到i之间的索引 j = random.randint(0, i) # 交换元素 self.array[i], self.array[j] = self.array[j], self.array[i] return self.array def shuffle_forward(self): """正向洗牌算法（同样正确）""" n = len(self.array) for i in range(n): # 随机选择i到n-1之间的索引 j = random.randint(i, n - 1) self.array[i], self.array[j] = self.array[j], self.array[i] return self.array # 验证洗牌算法的公平性 def test_shuffle_fairness(): """测试洗牌算法的公平性""" from collections import Counter arr = [1, 2, 3] position_counts = {1: Counter(), 2: Counter(), 3: Counter()} num_trials = 60000 for _ in range(num_trials): shuffle = ShuffleArray(arr) shuffled = shuffle.shuffle() for i, num in enumerate(shuffled): position_counts[num][i] += 1 # 每个数字出现在每个位置的概率应该接近1/3 print("位置分布统计：") for num in position_counts: print(f"数字 {num}: ", end="") for pos in range(3): prob = position_counts[num][pos] / num_trials print(f"位置{pos}: {prob:.3f} ", end="") print() # 调用测试 test_shuffle_fairness()

三、希尔排序（Shell Sort）

3.1 算法原理

希尔排序是插入排序的改进版，也称为缩小增量排序。它通过将原始数组分割成多个子序列，分别进行插入排序，随着增量逐渐减小，最终对整个数组进行一次插入排序。

核心思想：

1. 选择一个增量序列（如n/2, n/4, ..., 1）

2. 按增量分组，对每组进行插入排序

3. 减少增量，重复步骤2，直到增量为1

3.2 时间复杂度与空间复杂度

• 时间复杂度：

  • 最好情况：O(n log n)

  • 平均情况：取决于增量序列，一般为O(n^(1.3~2))

  • 最坏情况：O(n²)

• 空间复杂度：O(1)（原地排序）

3.3 希尔排序实现

python

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 def shell_sort_with_sedgewick_gap(arr): """使用Sedgewick增量序列的希尔排序（更高效）""" n = len(arr) # Sedgewick增量序列（部分） gaps = [929, 505, 209, 109, 41, 19, 5, 1] # 选择小于n的最大增量 gap_index = 0 while gap_index < len(gaps) and gaps[gap_index] > n: gap_index += 1 # 使用Sedgewick增量序列进行排序 for gap in gaps[gap_index:]: 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 return arr # 希尔排序性能测试 import time import random def performance_test(): """性能测试：希尔排序 vs 插入排序""" sizes = [1000, 5000, 10000] for size in sizes: arr = [random.randint(1, 10000) for _ in range(size)] # 希尔排序 arr_shell = arr.copy() start = time.time() shell_sort(arr_shell) shell_time = time.time() - start # 插入排序 def insertion_sort(arr): for i in range(1, len(arr)): 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 arr_insert = arr.copy() start = time.time() insertion_sort(arr_insert) insert_time = time.time() - start print(f"数组大小 {size}:") print(f" 希尔排序时间: {shell_time:.4f}秒") print(f" 插入排序时间: {insert_time:.4f}秒") print(f" 希尔排序比插入排序快 {insert_time/shell_time:.2f}倍") print() performance_test()

四、排序链表（Sort List）

4.1 问题描述

LeetCode 148. 排序链表：在O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序。

4.2 算法原理

使用归并排序对链表进行排序：

1. 使用快慢指针找到链表中点

2. 递归地对左右两部分进行排序

3. 合并两个已排序的链表

4.3 时间复杂度与空间复杂度

• 时间复杂度：O(n log n)

• 空间复杂度：O(log n)（递归栈空间），如果使用迭代归并可以做到O(1)

4.4 排序链表实现

python

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def sortList(self, head: ListNode) -> ListNode: """排序链表（递归归并排序）""" if not head or not head.next: return head # 使用快慢指针找到链表中点 slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next # 分割链表 mid = slow.next slow.next = None # 递归排序左右两部分 left = self.sortList(head) right = self.sortList(mid) # 合并已排序的链表 return self.merge(left, right) def merge(self, l1: ListNode, l2: ListNode) -> ListNode: """合并两个有序链表""" dummy = ListNode(0) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next def sortList_iterative(self, head: ListNode) -> ListNode: """排序链表（迭代归并排序，空间O(1)）""" if not head or not head.next: return head # 计算链表长度 length = 0 cur = head while cur: length += 1 cur = cur.next dummy = ListNode(0, head) # 从step=1开始，每次翻倍 step = 1 while step < length: prev, cur = dummy, dummy.next while cur: # 获取第一个子链表 left = cur for i in range(1, step): if cur.next: cur = cur.next else: break # 获取第二个子链表 right = cur.next cur.next = None # 切断第一个子链表 cur = right for i in range(1, step): if cur and cur.next: cur = cur.next else: break # 保存剩余部分 remaining = None if cur: remaining = cur.next cur.next = None # 切断第二个子链表 # 合并两个子链表 merged = self.merge(left, right) # 连接到已排序部分 prev.next = merged while prev.next: prev = prev.next # 继续处理剩余部分 cur = remaining step *= 2 return dummy.next # 辅助函数：创建链表和打印链表 def create_list(arr): """从数组创建链表""" dummy = ListNode(0) cur = dummy for val in arr: cur.next = ListNode(val) cur = cur.next return dummy.next def print_list(head): """打印链表""" res = [] while head: res.append(head.val) head = head.next print("->".join(map(str, res))) # 测试排序链表 arr = [4, 2, 1, 3, 5] head = create_list(arr) print("原始链表:") print_list(head) sol = Solution() sorted_head = sol.sortList(head) print("\n排序后链表:") print_list(sorted_head) # 测试迭代版本 arr2 = [-1, 5, 3, 4, 0] head2 = create_list(arr2) print("\n原始链表2:") print_list(head2) sorted_head2 = sol.sortList_iterative(head2) print("迭代排序后链表:") print_list(sorted_head2)

五、扑克牌问题

5.1 问题描述

给定一副牌，每张牌上写着一个整数。你需要判断是否可能将这些牌分成若干组，每组都有X张牌，且每组内的牌上都写着相同的整数。

5.2 算法原理

1. 统计每个数字出现的次数

2. 找到所有次数的最大公约数（GCD）

3. 如果GCD大于等于2，则可能分组

5.3 扑克牌问题实现

python

from collections import Counter from math import gcd from functools import reduce def hasGroupsSizeX(deck): """判断是否能将牌分成每组X张牌""" if len(deck) < 2: return False # 统计每个数字出现的次数 count = Counter(deck) # 计算所有次数的最大公约数 counts = list(count.values()) g = reduce(gcd, counts) return g >= 2 def poker_partition(deck): """扑克牌分组问题完整解法""" if len(deck) < 2: return False, [] # 统计频率 count = Counter(deck) # 找到最小频率 min_freq = min(count.values()) # 如果最小频率小于2，直接返回False if min_freq < 2: return False, [] # 尝试从2到最小频率的所有可能的X值 for X in range(2, min_freq + 1): # 检查所有频率是否都能被X整除 if all(freq % X == 0 for freq in count.values()): # 可以分组，构建分组结果 groups = [] temp_deck = deck.copy() num_groups = len(deck) // X for i in range(num_groups): group = [] # 选择X张相同数字的牌 for num, freq in list(count.items()): if freq >= X: group = [num] * X count[num] -= X if count[num] == 0: del count[num] break groups.append(group) return True, groups return False, [] # 测试扑克牌问题 test_cases = [ [1, 2, 3, 4, 4, 3, 2, 1], # True [1, 1, 1, 2, 2, 2, 3, 3], # False [1], # False [1, 1, 2, 2, 2, 2], # True [1, 1, 1, 1, 2, 2, 2, 2, 2, 2], # True ] print("扑克牌分组测试:") for i, deck in enumerate(test_cases): result, groups = poker_partition(deck) print(f"测试用例 {i+1}: {deck}") print(f" 是否可以分组: {result}") if result: print(f" 分组结果: {groups}") print()

六、有效三角形的个数

6.1 问题描述

LeetCode 611. 有效三角形的个数：给定一个包含非负整数的数组，统计可以组成三角形三条边的三元组个数。

三角形条件：对于三边a, b, c，需满足：

1. a + b > c

2. a + c > b

3. b + c > a

6.2 算法原理

高效解法（双指针法）：

1. 先将数组排序

2. 固定最长边nums[k]（从后向前遍历）

3. 使用双指针i和j分别指向数组开头和k-1位置

4. 如果nums[i] + nums[j] > nums[k]，则所有i到j-1之间的元素与j、k都能组成三角形

5. 移动指针直到遍历完所有可能

6.3 时间复杂度与空间复杂度

• 时间复杂度：O(n²)（排序O(n log n) + 双指针遍历O(n²)）

• 空间复杂度：O(1)（原地排序）或O(n)（如果需要复制数组）

6.4 有效三角形的个数实现

python

def triangleNumber(nums): """统计可以组成三角形的三元组个数""" if len(nums) < 3: return 0 # 排序数组 nums.sort() n = len(nums) count = 0 # 固定最长边 for k in range(n - 1, 1, -1): i, j = 0, k - 1 # 双指针查找 while i < j: if nums[i] + nums[j] > nums[k]: # 所有i到j-1之间的元素与j、k都能组成三角形 count += j - i j -= 1 else: i += 1 return count def triangleNumber_bruteforce(nums): """暴力解法（仅用于验证）""" n = len(nums) count = 0 for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): a, b, c = nums[i], nums[j], nums[k] if a + b > c and a + c > b and b + c > a: count += 1 return count def triangleNumber_with_indices(nums): """返回所有有效的三角形三元组""" if len(nums) < 3: return 0, [] nums_sorted = sorted(nums) n = len(nums_sorted) count = 0 triangles = [] # 固定最长边 for k in range(n - 1, 1, -1): i, j = 0, k - 1 while i < j: if nums_sorted[i] + nums_sorted[j] > nums_sorted[k]: # 记录所有有效的三元组 for x in range(i, j): triangles.append([nums_sorted[x], nums_sorted[j], nums_sorted[k]]) count += 1 j -= 1 else: i += 1 return count, triangles # 测试有效三角形的个数 test_cases = [ [2, 2, 3, 4], [4, 2, 3, 4], [1, 2, 3, 4, 5, 6], [7, 8, 9, 10], [0, 0, 0], # 不能组成三角形 ] print("有效三角形的个数测试:") for i, nums in enumerate(test_cases): count = triangleNumber(nums) count_bf = triangleNumber_bruteforce(nums) count_result, triangles = triangleNumber_with_indices(nums) print(f"测试用例 {i+1}: {nums}") print(f" 双指针法结果: {count}") print(f" 暴力法验证: {count_bf}") print(f" 有效三元组数量: {count_result}") if triangles and len(triangles) <= 10: # 限制输出数量 print(f" 部分有效三元组: {triangles[:5]}...") print()

七、综合比较与面试技巧

7.1 排序算法对比

7.2 面试常见问题

1. 如何选择基准元素？

   • 选择第一个/最后一个元素：简单但可能导致最坏情况（已排序数组）。

   • 随机选择：随机选择一个元素作为基准，避免最坏情况，但随机数生成有开销。

   • 三数取中法：选择第一个、中间和最后一个元素的中位数作为基准，有效避免最坏情况。

2. 如何处理重复元素？

   • 三路快排：将数组分为小于、等于和大于基准三部分，递归排序小于和大于部分，等于部分已排序。

   • 稳定分区算法：保证相同元素的相对顺序不变，但实现复杂，通常快排不稳定。

3. 链表排序为什么常用归并排序？

   • 链表随机访问代价高，而快速排序需要频繁随机访问，不适合链表。

   • 归并排序只需要顺序访问，适合链表结构。

   • 归并排序可以做到O(1)空间复杂度（迭代归并），而数组归并需要额外空间。

4. 洗牌算法为什么是公平的？

   • 每个元素出现在每个位置的概率相等。对于有n个元素的数组，第i个元素被放在位置j（0≤j≤i）的概率是1/(i+1)。通过数学归纳法可以证明每个元素出现在每个位置的概率都是1/n。

5. 如何证明快速排序的平均时间复杂度是O(n log n)？

   • 通过递推式T(n) = T(k) + T(n-k-1) + O(n)，其中k是分割后左半部分的元素个数。假设k在0到n-1均匀分布，可以证明T(n)=O(n log n)。

6. 希尔排序的增量序列如何选择？

   • 希尔增量：n/2, n/4, ..., 1，最坏时间复杂度O(n²)。

   • Hibbard增量：1, 3, 7, ..., 2^k-1，最坏时间复杂度O(n^(3/2))。

   • Sedgewick增量：1, 5, 19, 41, 109, ...，最坏时间复杂度O(n^(4/3))，平均复杂度约为O(n^(7/6))。

7. 排序算法的稳定性有什么意义？

   • 稳定性保证了相等元素的相对顺序不变。这在多关键字排序中很重要，例如先按姓名排序，再按年龄排序，那么相同年龄的人姓名仍然有序。

8. 在什么情况下应该使用哪种排序算法？

   • 小规模数据：插入排序（简单且稳定）。

   • 大规模数据且要求稳定：归并排序。

   • 大规模数据且对稳定性无要求：快速排序（平均最快）。

   • 链表排序：归并排序。

   • 内存受限：堆排序或希尔排序。

   • 数据基本有序：插入排序或冒泡排序。

7.3 实战练习题目详解

题目一：LeetCode 215. 数组中的第K个最大元素

问题描述

在未排序的数组中找到第k个最大的元素。

解法思路：快速选择算法

快速选择是快速排序的变种，每次分区后只需要在一边递归查找。

python

def findKthLargest(nums, k): """快速选择算法找第k大元素""" # 转换问题：第k大 = 第len(nums)-k+1小 k_smallest = len(nums) - k def quick_select(left, right): """快速选择辅助函数""" # 随机选择基准 import random pivot_idx = random.randint(left, right) # 将基准交换到最右边 nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] # 分区操作 store_idx = left for i in range(left, right): if nums[i] < nums[right]: # 小于基准的放在左边 nums[store_idx], nums[i] = nums[i], nums[store_idx] store_idx += 1 # 将基准放到正确位置 nums[store_idx], nums[right] = nums[right], nums[store_idx] # 判断基准位置与k的关系 if store_idx == k_smallest: return nums[store_idx] elif store_idx > k_smallest: return quick_select(left, store_idx - 1) else: return quick_select(store_idx + 1, right) return quick_select(0, len(nums) - 1) def findKthLargest_heap(nums, k): """使用堆找第k大元素""" import heapq # 建立最小堆，保持堆大小为k min_heap = [] for num in nums: heapq.heappush(min_heap, num) if len(min_heap) > k: heapq.heappop(min_heap) # 弹出最小的 return min_heap[0] # 堆顶是第k大的元素 # 测试 nums = [3, 2, 1, 5, 6, 4] k = 2 print(f"数组: {nums}") print(f"第{k}大的元素(快速选择): {findKthLargest(nums, k)}") print(f"第{k}大的元素(堆): {findKthLargest_heap(nums.copy(), k)}")

题目二：LeetCode 75. 颜色分类

问题描述

给定一个包含红色、白色和蓝色，一共n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。

解法思路：三路快排

python

def sortColors(nums): """颜色分类：三路快排思想""" # 三指针法 left = 0 # 红色区域的右边界 right = len(nums) - 1 # 蓝色区域的左边界 i = 0 # 当前遍历指针 while i <= right: if nums[i] == 0: # 红色 nums[left], nums[i] = nums[i], nums[left] left += 1 i += 1 elif nums[i] == 2: # 蓝色 nums[right], nums[i] = nums[i], nums[right] right -= 1 # 注意：这里不增加i，因为交换过来的元素还没检查 else: # 白色 i += 1 # 测试 colors = [2, 0, 2, 1, 1, 0] print(f"\n原始颜色数组: {colors}") sortColors(colors) print(f"排序后: {colors}")

题目三：LeetCode 912. 排序数组

问题描述

给你一个整数数组nums，请你将该数组升序排列。

多种排序算法实现

python

def sortArray(nums): """多种排序算法实现""" # 方法1：归并排序 def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) # 合并两个有序数组 result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result # 方法2：堆排序 def heap_sort(arr): 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) 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 # 返回归并排序结果 return merge_sort(nums) # 测试 nums = [5, 2, 3, 1] print(f"\n原始数组: {nums}") print(f"排序后: {sortArray(nums)}")

题目四：LeetCode 56. 合并区间

问题描述

以数组 intervals 表示若干个区间的集合，请合并所有重叠的区间。

解法思路：排序后合并

python

def merge(intervals): """合并重叠区间""" if not intervals: return [] # 按区间起点排序 intervals.sort(key=lambda x: x[0]) merged = [] current = intervals[0] for interval in intervals[1:]: # 如果当前区间与下一个区间重叠 if current[1] >= interval[0]: # 合并区间 current[1] = max(current[1], interval[1]) else: # 不重叠，保存当前区间，开始新区间 merged.append(current) current = interval merged.append(current) return merged # 测试 intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] print(f"\n原始区间: {intervals}") print(f"合并后: {merge(intervals)}")

题目五：LeetCode 179. 最大数

问题描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

解法思路：自定义排序

python

def largestNumber(nums): """组成最大数""" # 将数字转换为字符串 str_nums = list(map(str, nums)) # 自定义比较函数 def compare(x, y): # 比较x+y和y+x if x + y > y + x: return -1 # x应该排在y前面 elif x + y < y + x: return 1 # y应该排在x前面 else: return 0 # Python 3中sort不再直接支持cmp参数，使用functools.cmp_to_key from functools import cmp_to_key str_nums.sort(key=cmp_to_key(compare)) # 拼接结果 result = ''.join(str_nums) # 处理前导0的情况 return '0' if result[0] == '0' else result # 测试 nums = [3, 30, 34, 5, 9] print(f"\n原始数字: {nums}") print(f"最大数: {largestNumber(nums)}")

7.4 面试技巧与策略

1. 算法面试四步法

python

""" 面试解决算法问题的四步法： 1. 理解问题：确保完全理解题目要求 2. 思考方案：想清楚可能的解法，分析复杂度 3. 编码实现：清晰、模块化地实现 4. 测试验证：测试边界条件和典型用例 """ class InterviewStrategy: """面试策略示例""" def solve_problem(self, problem_description): """解决问题的框架""" # 第一步：理解问题 print("1. 理解问题：") print(f" - 输入是什么？") print(f" - 输出是什么？") print(f" - 有什么约束条件？") # 第二步：思考方案 print("\n2. 思考方案：") print(f" - 暴力解法是什么？复杂度如何？") print(f" - 能否优化？有哪些数据结构可用？") print(f" - 有没有类似的经典问题？") # 第三步：编码实现 print("\n3. 编码实现：") print(f" - 写出清晰的代码") print(f" - 添加必要的注释") print(f" - 使用有意义的变量名") # 第四步：测试验证 print("\n4. 测试验证：") print(f" - 测试正常情况") print(f" - 测试边界情况") print(f" - 测试性能")

2. 复杂度分析要点

python

def complexity_analysis(): """复杂度分析要点""" complexities = { "O(1)": "常数时间，最快", "O(log n)": "对数时间，非常高效", "O(n)": "线性时间，良好", "O(n log n)": "线性对数时间，排序算法的典型复杂度", "O(n²)": "平方时间，嵌套循环", "O(2^n)": "指数时间，避免使用", "O(n!)": "阶乘时间，非常慢" } print("常见时间复杂度：") for comp, desc in complexities.items(): print(f" {comp}: {desc}")

3. 排序算法选择指南

python

def choose_sorting_algorithm(data, requirements): """根据需求选择排序算法""" n = len(data) # 算法选择逻辑 if n <= 10: return "插入排序：小数据量效率高" elif requirements.get("stable", False): return "归并排序：稳定排序" elif requirements.get("space_constrained", False): return "堆排序：原地排序，O(1)空间" elif requirements.get("linked_list", False): return "归并排序：适合链表" elif requirements.get("worst_case", False): return "归并排序或堆排序：保证O(n log n)最坏情况" else: return "快速排序：平均性能最好"

7.5 综合练习

综合题目：实现多功能排序工具类

python

class SortingToolkit: """多功能排序工具类""" def __init__(self): self.algorithms = { "quick_sort": self.quick_sort, "merge_sort": self.merge_sort, "heap_sort": self.heap_sort, "tim_sort": self.tim_sort } def quick_sort(self, 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 self.quick_sort(left) + middle + self.quick_sort(right) def merge_sort(self, arr): """归并排序""" if len(arr) <= 1: return arr mid = len(arr) // 2 left = self.merge_sort(arr[:mid]) right = self.merge_sort(arr[mid:]) return self._merge(left, right) def _merge(self, left, right): """合并两个有序数组""" result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result def heap_sort(self, arr): """堆排序""" import heapq # Python的heapq默认是最小堆，我们需要最大堆 max_heap = [-x for x in arr] heapq.heapify(max_heap) result = [] while max_heap: result.append(-heapq.heappop(max_heap)) return result[::-1] # 反转得到升序 def tim_sort(self, arr): """TimSort（Python内置排序使用）""" # 这里简化实现，实际使用Python内置排序 return sorted(arr) def benchmark(self, arr, algorithm_name): """性能测试""" import time if algorithm_name not in self.algorithms: raise ValueError(f"未知算法: {algorithm_name}") arr_copy = arr.copy() start = time.time() result = self.algorithms[algorithm_name](arr_copy) end = time.time() return result, end - start def compare_all(self, arr): """比较所有算法的性能""" print(f"数组大小: {len(arr)}") print("-" * 40) for algo_name in self.algorithms: _, time_taken = self.benchmark(arr, algo_name) print(f"{algo_name:15s}: {time_taken:.6f} 秒") # 使用示例 toolkit = SortingToolkit() test_data = [random.randint(1, 10000) for _ in range(1000)] print("排序算法性能比较：") toolkit.compare_all(test_data)