企业官网建设流程全解析

平度做网站,阿里云服务器发布网站,建站用企业级主机好还是服务器,印刷行业网站建设一、快速排序#xff08;Quick Sort#xff09;1.1 算法原理快速排序采用分治策略#xff0c;核心思想是选择一个基准元素#xff0c;将数组分为两部分#xff0c;使得左侧所有元素都小于等于基准#xff0c;右侧所有元素都大于等于基准#xff0c;然后递归地对左右两部…一、快速排序Quick Sort1.1 算法原理快速排序采用分治策略核心思想是选择一个基准元素将数组分为两部分使得左侧所有元素都小于等于基准右侧所有元素都大于等于基准然后递归地对左右两部分进行排序。具体步骤选择基准值pivot分区操作将数组重新排列所有小于基准的元素放在前面大于基准的放在后面递归地对左右两个子数组进行快速排序1.2 时间复杂度分析最好情况每次分区都能将数组均匀分成两部分递归深度为O(log n)每层比较O(n)次时间复杂度为O(n log n)平均情况O(n log n)最坏情况每次选择的基准都是最大或最小值导致分区极度不平衡时间复杂度为O(n²)空间复杂度O(log n)递归调用栈1.3 快速排序实现pythondef 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, low0, highNone): 原地快速排序节省空间 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, low0, highNone): 三路快速排序适用于有大量重复元素的数组 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 Algorithm2.1 算法原理洗牌算法Fisher-Yates Shuffle是一种公平的随机排列算法保证每个排列出现的概率相等。核心思想从最后一个元素开始随机选择当前位置及之前的某个位置进行交换然后向前移动。2.2 时间复杂度与空间复杂度时间复杂度O(n)空间复杂度O(1)原地洗牌2.3 洗牌算法实现pythonimport 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 Sort3.1 算法原理希尔排序是插入排序的改进版也称为缩小增量排序。它通过将原始数组分割成多个子序列分别进行插入排序随着增量逐渐减小最终对整个数组进行一次插入排序。核心思想选择一个增量序列如n/2, n/4, ..., 1按增量分组对每组进行插入排序减少增量重复步骤2直到增量为13.2 时间复杂度与空间复杂度时间复杂度最好情况O(n log n)平均情况取决于增量序列一般为O(n^(1.3~2))最坏情况O(n²)空间复杂度O(1)原地排序3.3 希尔排序实现pythondef 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 List4.1 问题描述LeetCode 148. 排序链表在O(n log n)时间复杂度和常数级空间复杂度下对链表进行排序。4.2 算法原理使用归并排序对链表进行排序使用快慢指针找到链表中点递归地对左右两部分进行排序合并两个已排序的链表4.3 时间复杂度与空间复杂度时间复杂度O(n log n)空间复杂度O(log n)递归栈空间如果使用迭代归并可以做到O(1)4.4 排序链表实现pythonclass ListNode: def __init__(self, val0, nextNone): 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) # 从step1开始每次翻倍 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 算法原理统计每个数字出现的次数找到所有次数的最大公约数GCD如果GCD大于等于2则可能分组5.3 扑克牌问题实现pythonfrom 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测试用例 {i1}: {deck}) print(f 是否可以分组: {result}) if result: print(f 分组结果: {groups}) print()六、有效三角形的个数6.1 问题描述LeetCode 611. 有效三角形的个数给定一个包含非负整数的数组统计可以组成三角形三条边的三元组个数。三角形条件对于三边a, b, c需满足a b ca c bb c a6.2 算法原理高效解法双指针法先将数组排序固定最长边nums[k]从后向前遍历使用双指针i和j分别指向数组开头和k-1位置如果nums[i] nums[j] nums[k]则所有i到j-1之间的元素与j、k都能组成三角形移动指针直到遍历完所有可能6.3 时间复杂度与空间复杂度时间复杂度O(n²)排序O(n log n) 双指针遍历O(n²)空间复杂度O(1)原地排序或O(n)如果需要复制数组6.4 有效三角形的个数实现pythondef 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测试用例 {i1}: {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 排序算法对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景快速排序O(n log n)O(n²)O(log n)不稳定通用排序平均性能好希尔排序O(n^(1.3~2))O(n²)O(1)不稳定中等规模数据内存受限归并排序O(n log n)O(n log n)O(n)稳定链表排序需要稳定性堆排序O(n log n)O(n log n)O(1)不稳定实时系统最坏情况有保证插入排序O(n²)O(n²)O(1)稳定小规模或基本有序数据7.2 面试常见问题如何选择基准元素选择第一个/最后一个元素简单但可能导致最坏情况已排序数组。随机选择随机选择一个元素作为基准避免最坏情况但随机数生成有开销。三数取中法选择第一个、中间和最后一个元素的中位数作为基准有效避免最坏情况。如何处理重复元素三路快排将数组分为小于、等于和大于基准三部分递归排序小于和大于部分等于部分已排序。稳定分区算法保证相同元素的相对顺序不变但实现复杂通常快排不稳定。链表排序为什么常用归并排序链表随机访问代价高而快速排序需要频繁随机访问不适合链表。归并排序只需要顺序访问适合链表结构。归并排序可以做到O(1)空间复杂度迭代归并而数组归并需要额外空间。洗牌算法为什么是公平的每个元素出现在每个位置的概率相等。对于有n个元素的数组第i个元素被放在位置j0≤j≤i的概率是1/(i1)。通过数学归纳法可以证明每个元素出现在每个位置的概率都是1/n。如何证明快速排序的平均时间复杂度是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)。希尔排序的增量序列如何选择希尔增量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.3 实战练习题目详解题目一LeetCode 215. 数组中的第K个最大元素问题描述在未排序的数组中找到第k个最大的元素。解法思路快速选择算法快速选择是快速排序的变种每次分区后只需要在一边递归查找。pythondef findKthLargest(nums, k): 快速选择算法找第k大元素 # 转换问题第k大 第len(nums)-k1小 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个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色的顺序排列。解法思路三路快排pythondef 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请你将该数组升序排列。多种排序算法实现pythondef 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 表示若干个区间的集合请合并所有重叠的区间。解法思路排序后合并pythondef merge(intervals): 合并重叠区间 if not intervals: return [] # 按区间起点排序 intervals.sort(keylambda 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. 最大数问题描述给定一组非负整数重新排列它们的顺序使之组成一个最大的整数。解法思路自定义排序pythondef largestNumber(nums): 组成最大数 # 将数字转换为字符串 str_nums list(map(str, nums)) # 自定义比较函数 def compare(x, y): # 比较xy和yx 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(keycmp_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. 复杂度分析要点pythondef 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. 排序算法选择指南pythondef 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 综合练习综合题目实现多功能排序工具类pythonclass 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): TimSortPython内置排序使用 # 这里简化实现实际使用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)