python 常见的排序算法实现汇总

2023-07-18 10:29:03 83

排序分为两类，比较类排序和非比较类排序，比较类排序通过比较来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)；非比较类排序可以突破基于比较排序的时间下界，缺点就是一般只能用于整型相关的数据类型，需要辅助的额外空间。

要求能够手写时间复杂度位O(nlogn)的排序算法：快速排序、归并排序、堆排序

1.冒泡排序

思想：相邻的两个数字进行比较，大的向下沉，最后一个元素是最大的。列表右边先有序。

时间复杂度$O(n^2)$，原地排序，稳定的

defbubble_sort(li:list):
foriinrange(len(li)-1):
forjinrange(i+1,len(li)):
ifli[i]>li[j]:
li[i],li[j]=li[j],li[i]

2.选择排序

思想：首先找到最小元素，放到排序序列的起始位置，然后再从剩余元素中继续寻找最小元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。列表左边先有序。

时间复杂度$O(n^2)$，原地排序，不稳定

defselect_sort(nums:list):
foriinrange(len(nums)-1):
min_index=i
forjinrange(i+1,len(nums)):
ifnums[j]
3.插入排序
思想：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。列表左边先有序。
时间复杂度$O(n^2)$，原地排序，稳定
definsert_sort(nums:list):
foriinrange(len(nums)):
current=nums[i]
pre_index=i-1
whilepre_index>=0andnums[pre_index]>current:
nums[pre_index+1]=nums[pre_index]
pre_index-=1
nums[pre_index+1]=current
4.希尔排序
思想：插入排序的改进版，又称缩小增量排序，将待排序的列表按下标的一定增量分组，每组分别进行直接插入排序，增量逐渐减小，直到为1，排序完成
时间复杂度$O(n^{1.5})$，原地排序，不稳定
defshell_sort(nums:list):
gap=len(nums)>>1
whilegap>0:
foriinrange(gap,len(nums)):
current=nums[i]
pre_index=i-gap
whilepre_index>=0andnums[pre_index]>current:
nums[pre_index+gap]=nums[pre_index]
pre_index-=gap
nums[pre_index+gap]=current
gap>>=1
5.快速排序
思想：递归，列表中取出第一个元素，作为标准，把比第一个元素小的都放在左侧，把比第一个元素大的都放在右侧，递归完成时就是排序结束的时候
时间复杂度$O(nlogn)$，空间复杂度$O(logn)$，不稳定
defquick_sort(li:list):
ifli==[]:
return[]
first=li[0]
#推导式实现
left=quick_sort([lforlinli[1:]ifl=first])
returnleft+[first]+right
6.归并排序
思想：分治算法，拆分成子序列，使用归并排序，将排序好的子序列合并成一个最终的排序序列。关键在于怎么合并：设定两个指针，最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放到合并空间，并将该指针移到下一位置，直到某一指针超出序列尾，将另一序列所剩下的所有元素直接复制到合并序列尾。
时间复杂度$O(nlogn)$，空间复杂度O(n)，不稳定
二路归并
defmerge_sort(nums:list):
iflen(nums)<=1:
returnnums
mid=len(nums)>>1
left=merge_sort(nums[:mid])#拆分子问题
right=merge_sort(nums[mid:])

defmerge(left,right):#如何归并
res=[]
l,r=0,0
whilel
7.堆排序


思想：根节点最大，大顶堆，对应升序，根节点最小，小顶堆。

构建大根堆，完全二叉树结构，初始无序
最大堆调整，进行堆排序。将堆顶元素与最后一个元素交换，此时后面有序



时间复杂度$O(nlogn)$，原地排序，稳定
defheap_sort(nums:list):
defheapify(parent_index,length,nums):
temp=nums[parent_index]#根节点的值
chile_index=2*parent_index+1#左节点，再加一为右节点
whilechile_indexnums[chile_index]:
chile_index=chile_index+1
iftemp>nums[chile_index]:
break
nums[parent_index]=nums[chile_index]#使得根节点最大
parent_index=chile_index
chile_index=2*parent_index+1
nums[parent_index]=temp

foriinrange((len(nums)-2)>>1,-1,-1):
heapify(i,len(nums),nums)#1.建立大根堆
forjinrange(len(nums)-1,0,-1):
nums[j],nums[0]=nums[0],nums[j]
heapify(0,j,nums)#2.堆排序，为升序

if__name__=='__main__':
nums=[89,3,3,2,5,45,33,67]#[2,3,3,5,33,45,67,89]
heap_sort(nums)
print(nums)
以上就是python常见的排序算法实现汇总的详细内容，更多关于python排序算法的资料请关注毛票票其它相关文章！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

python 常见的排序算法实现汇总

热门推荐

随机推荐