Python 六种常用排序算法实现详解
本文详细解析 Python 中六种基础排序算法的实现逻辑与代码。涵盖插入、冒泡、快速、选择、归并及希尔排序，通过具体示例展示各算法的核心机制，如双指针交换、递归分治及步长递减等，为开发者提供清晰的学习参考与实战代码支持。
Python 排序算法概述
本文重点介绍 Python 中几种常见排序算法的具体实现方式，文中提供了详细的示例代码，旨在为读者的学习或工作提供有价值的参考。
排序是计算机编程中必须掌握的基础算法之一，使用有序的数据结构能够显著提升数据处理效率。
插入排序与冒泡排序
1. 插入排序
插入排序的基本假设是：当前已处理的序列部分已经是有序的。新元素会被插入到其正确的位置，从而保持整个序列的有序性。
def insertion_sort(old_list):
n=len(old_list)
k=0
for i in range(1,n):
temp=old_list[i]
j=i
while j>0 and temp<old_list[j-1]:
old_list[j]=old_list[j-1]
j=j-1
old_list[j]=temp
return old_list2. 冒泡排序
冒泡排序通过遍历序列来工作。在遍历过程中，如果发现相邻的两个元素中左边的值大于右边的值，则交换它们的位置。经过一次完整遍历后，最大的元素会被移动到序列末尾。随后进行第二次遍历，重复此过程，直到整个序列变为有序。
冒泡排序代码实现
def bubble_sort(old_list):
n=len(old_list)
for i in range(n-1):
for j in range(n-1-i):
if old_list[j]>old_list[j+1]:
old_list[j],old_list[j+1]=old_list[j+1],old_list[j]
return old_list快速排序原理与实现
3. 快速排序
快速排序的核心实现是设置两个游标，分别从序列的前端和后端向中间移动。如果左侧游标指向的数据大于右侧游标指向的数据，则交换这两个数据。当两个游标指向同一个数据时，第一趟遍历结束。此时，该数据左侧的所有元素都小于它，右侧的所有元素都大于它。
接下来，算法会对游标分隔出的前后两个子序列分别进行递归操作，直至所有子序列有序。
快速排序代码示例
def quick_sort(list,low,high):
i=low
j=high
if i >= j:
return list
key=list[i]
while i < j:
while i < j and list[j]>=key:
j = j - 1
list[i]=list[j]
while i < j and list[i]<=key:
i = i + 1
list[j]=list[i]
list[i]=key
quick_sort(list,low,i-1)
quick_sort(list,j+1,high)
return list选择排序逻辑与代码
4. 选择排序
选择排序的原理是：首先找到起始数组中最小的元素，将其交换到索引 i=0 的位置；接着在剩余元素中找到最小的元素，交换到 i=1 的位置；依此类推，直到找到倒数第二个元素（即第二大的元素），将其交换到索引 n-2 的位置。此时，整个数组的排序即告完成。
选择排序代码示例
def select_sort(list):
length=len(list)
for i in range(length):
min_index=i
for j in range(i,length):
if list[j]<list[min_index]:
min_index=j
list[i],list[min_index]=list[min_index],list[i]
return list归并排序机制与代码
5. 归并排序
归并排序采用分治策略，对数组进行递归拆分，直到子数组无法再拆分为止。然后，分别对最小粒度的子数组进行合并，再逐步合并稍大的数组，直到最终合成一个完整的有序大数组。该算法通常由两个函数配合完成：一个负责递归拆分，另一个负责排序与合并。
归并排序代码示例
def merge_sort(list):
if len(list)<=1:
return list
mid=int(len(list)/2)
left=merge_sort(list[:mid])
right=merge_sort(list[mid:])
return merge(left,right)
def merge(list1,list2):
list=[]
i,j=0,0
while i<len(list1) and j<len(list2):
if list1[i]<list2[j]:
list.append(list1[i])
i=i+1
elif list1[i]>=list2[j]:
list.append(list2[j])
j=j+1
list.extend(list1[i:])
list.extend(list2[j:])
return list希尔排序与总结
6. 希尔排序
希尔排序代码示例
def shell_sort(nums):
step = len(nums)/2
while step > 0:
for i in range(step, len(nums)):
while i >= step and nums[i-step] > nums[i]:
nums[i], nums[i-step] = nums[i-step], nums[i]
i -= step
step = step/2
return nums以上就是本文介绍的全部内容，希望对读者的学习有所帮助，也欢迎大家继续支持本站获取更多技术资源。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
