Python 中的排序算法
什么是排序?
排序是指根据数据项之间的线性关系,以特定顺序(通常是升序或降序)排列数据的过程。
为什么我们需要排序?
排序在处理结构化数据时至关重要,因为它可以实现高效的数据检索、简化数据分析并增强整体数据管理。
排序算法
这篇文章涵盖了以下排序算法:冒泡排序、选择排序、插入排序、合并排序和快速排序。
冒泡排序
冒泡排序重复遍历数组,比较相邻元素,如果顺序错误则交换它们。这个过程一直持续到数组排序完毕,较大的元素“冒泡”到末尾。
算法
第 1 步:开始
步骤 2:i = 0
步骤3:如果i
步骤 4:j = 0
步骤5:如果j<; length(array) - i - 1,转到步骤6;否则转到步骤 3
步骤6:如果array[j]> array[j + 1],转到步骤7;否则转到步骤 8
步骤7:交换数组[j]和数组[j + 1]
步骤8:递增j;转到步骤 5
步骤9:增加i;转到步骤 3
第10步:结束
代码
def bubble_sort(arr): print("Array Before Sorting: ", end='') print(arr) for i in range(len(arr)): for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] print("Array After Sorting: ", end='') print(arr) # Main bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
时间复杂度
最佳情况:O(n)
平均情况:O(n^2)
最坏情况:O(n^2)
选择排序
选择排序查找数组未排序部分中的最小值,并将其放置在该部分的开头。
算法
第 1 步:开始
步骤 2:i = 0
步骤3:如果i
步骤4:minimum_value = i; j = i + 1
步骤5:如果j<1。 length(数组),转到步骤6;否则转到步骤 9
步骤 6:如果 array[minimum_value] > array[j],转到步骤7;否则转到步骤 8
步骤 7:minimum_value = j
步骤8:递增j;转到步骤 5
第9步:交换数组[minimum_value]和数组[i]
步骤10:增加i;转到步骤 3
第11步:结束
代码
def selection_sort(arr): print("Array Before Sorting: ", end='') print(arr) for i in range(len(arr) - 1): min_val = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_val]: min_val = j arr[i], arr[min_val] = arr[min_val], arr[i] print("Array After Sorting: ", end='') print(arr) # Main selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
时间复杂度
最佳情况:O(n^2)
平均情况:O(n^2)
最坏情况:O(n^2)
插入排序
插入排序通过从未排序部分取出每个元素并将其插入到已排序部分的正确位置来构建排序数组,一次一个元素。
算法
第 1 步:开始
步骤 2:i = 1
步骤3:如果i<; len(arr),转到步骤4;否则转到步骤 12
第四步:key = arr[i]
步骤 5:j = i - 1
步骤6:如果j>=0且arr[j]>键,转到步骤7;否则转到步骤 10
步骤7:arr[j + 1] = arr[j]
步骤 8:将 j 减 1
第9步:转到第6步
第10步:arr[j + 1] = key
步骤11:i加1;转到步骤 3
第12步:结束
代码
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) insertion_sort(arr) print("Array After Sorting:", arr)
时间复杂度
最佳情况:O(n)
平均情况:O(n^2)
最坏情况:O(n^2)
归并排序
合并排序是一种分而治之的算法,它递归地将数组划分为更小的子数组,对它们进行排序,然后将它们合并在一起。
算法
合并排序算法
第 1 步:开始
步骤2:如果length(array)
第三步:mid_point = length(array) // 2
步骤 4:left_half = array[:mid_point]
第5步:right_half = array[mid_point:]
第6步:sorted_left = merge_sort(left_half)
第7步:sorted_right = merge_sort(right_half)
步骤8:返回merge(sorted_left,sorted_right)
第9步:结束
合并函数
第 1 步:开始
步骤2:sorted_merge = []
步骤 3:l = 0,r = 0
步骤4:如果l
步骤5:若left[l]
第6步:将left[l]添加到sorted_merge中;将 l 加 1
步骤7:将right[r]添加到sorted_merge;将 r 加 1
第8步:转到第4步
步骤9:如果l
第10步:将left[l]添加到sorted_merge中;将 l 加 1
第11步:转到第9步
步骤12:如果r<1 len(右),转到步骤13;否则转到步骤 15
第13步:将right[r]添加到sorted_merge中;将 r 加 1
第14步:转到第12步
第15步:返回sorted_merge
第16步:结束
代码
def merge(left, right): sorted_merge = [] l = r = 0 while l < len(left) and r < len(right): if left[l] <= right[r]: sorted_merge.append(left[l]) l += 1 else: sorted_merge.append(right[r]) r += 1 while l < len(left): sorted_merge.append(left[l]) l += 1 while r < len(right): sorted_merge.append(right[r]) r += 1 return sorted_merge def merge_sort(arr): if len(arr) <= 1: return arr mid_point = len(arr) // 2 left_half = arr[:mid_point] right_half = arr[mid_point:] sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) return merge(sorted_left, sorted_right) # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) arr = merge_sort(arr) print("Array After Sorting:", arr)
时间复杂度
最佳情况:O(n log n)
平均情况:O(n log n)
最坏情况:O(n log n)
Quick Sort
Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.
Algorithm
Quick Sort
Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End
Partition Function
Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End
Code
def partition(arr, low, high): pivot = arr[high] left = low right = high - 1 while left <= right: if arr[left] > pivot and arr[right] < pivot: arr[left], arr[right] = arr[right], arr[left] if arr[left] <= pivot: left += 1 if arr[right] >= pivot: right -= 1 arr[left], arr[high] = arr[high], arr[left] return left def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high) # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) quicksort(arr, 0, len(arr) - 1) print("Array After Sorting:", arr)
Time Complexity
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
以上是Python 中的排序算法的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

Python适合数据科学、Web开发和自动化任务,而C 适用于系统编程、游戏开发和嵌入式系统。 Python以简洁和强大的生态系统着称,C 则以高性能和底层控制能力闻名。

Python在游戏和GUI开发中表现出色。1)游戏开发使用Pygame,提供绘图、音频等功能,适合创建2D游戏。2)GUI开发可选择Tkinter或PyQt,Tkinter简单易用,PyQt功能丰富,适合专业开发。

Python更易学且易用,C 则更强大但复杂。1.Python语法简洁,适合初学者,动态类型和自动内存管理使其易用,但可能导致运行时错误。2.C 提供低级控制和高级特性,适合高性能应用,但学习门槛高,需手动管理内存和类型安全。

要在有限的时间内最大化学习Python的效率,可以使用Python的datetime、time和schedule模块。1.datetime模块用于记录和规划学习时间。2.time模块帮助设置学习和休息时间。3.schedule模块自动化安排每周学习任务。

Python在开发效率上优于C ,但C 在执行性能上更高。1.Python的简洁语法和丰富库提高开发效率。2.C 的编译型特性和硬件控制提升执行性能。选择时需根据项目需求权衡开发速度与执行效率。

pythonlistsarepartofthestAndArdLibrary,herilearRaysarenot.listsarebuilt-In,多功能,和Rused ForStoringCollections,而EasaraySaraySaraySaraysaraySaraySaraysaraySaraysarrayModuleandleandleandlesscommonlyusedDduetolimitedFunctionalityFunctionalityFunctionality。

Python在自动化、脚本编写和任务管理中表现出色。1)自动化:通过标准库如os、shutil实现文件备份。2)脚本编写:使用psutil库监控系统资源。3)任务管理:利用schedule库调度任务。Python的易用性和丰富库支持使其在这些领域中成为首选工具。

每天学习Python两个小时是否足够?这取决于你的目标和学习方法。1)制定清晰的学习计划,2)选择合适的学习资源和方法,3)动手实践和复习巩固,可以在这段时间内逐步掌握Python的基本知识和高级功能。
