python实现经典排序算法的示例代码

2023-07-05 19:28:02 80

以下排序算法最终结果都默认为升序排列，实现简单，没有考虑特殊情况，实现仅表达了算法的基本思想。

冒泡排序

内层循环中相邻的元素被依次比较，内层循环第一次结束后会将最大的元素移到序列最右边，第二次结束后会将次大的元素移到最大元素的左边，每次内层循环结束都会将一个元素排好序。

defbubble_sort(arr):
length=len(arr)
foriinrange(length):
forjinrange(length-i-1):
ifarr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
returnarr

选择排序

每次内层循环都会得到一个当前最小的元素，并将其放到合适的位置。内层循环第一次结束后会将最小的元素交换到序列首位，第二次结束后会将第二小的元素交换到序列第二位，每次内层循环结束后都会将一个元素放在正确的顺序位置。

defselection_sort(arr):
length=len(arr)
foriinrange(length):
min_index=i
forjinrange(i+1,length):
ifarr[j]
插入排序


类比玩扑克牌时理牌的思想，从第一个元素开始，假设它是已经排好序的。然后开始处理第二个元素，如果比第一个元素小，则将其放到第一个元素左边，否则放在其右边，那么现在前两个元素以及排好序了，之后再依次处理剩余的元素。
definsertion_sort(arr):
length=len(arr)
foriinrange(1,length):
pre=i-1
current_value=arr[i]
whilepre>=0andarr[pre]>current_value:
arr[pre+1]=arr[pre]
pre-=1
arr[pre+1]=current_value
returnarr

希尔排序


希尔排序就是将插入排序的改进版本。插入排序中每次逐步比较元素，而希尔排序中则是从一个较大的步数开始比较，最后减小到一步。
defshell_sort(arr):
length=len(arr)
gap=length//2
whilegap>0:
foriinrange(gap,length):
pre=i-gap
current_value=arr[i]
whilepre>=0andarr[pre]>current_value:
arr[pre+gap]=arr[pre]
pre-=gap
arr[pre+gap]=current_value
gap=gap//2
returnarr

归并排序


先将序列前半部分排好序，再将序列后半部分排好序，之后再将这两部分合并得到最终的序列，具体实现为递归地将序列分为两部分，分别排序后再合并。
defmerge(left,right):
result=[]
whilelen(left)>0andlen(right)>0:
ifleft[0]0:
result.extend(left[:])
iflen(right)>0:
result.extend(right[:])
returnresult


defmerge_sort(arr):
iflen(arr)<2:
returnarr
middle=len(arr)//2
returnmerge(merge_sort(arr[:middle]),merge_sort(arr[middle:]))


快速排序


取一个元素，将比它小的元素都移到它左侧，将比它大的元素都移到它右侧，并递归地处理它左侧的序列和右侧的序列。
defpartition(arr,left=None,right=None):
pivot=left
index=pivot+1
foriinrange(index,right+1):
ifarr[i]
堆排序


首先构建一个最大堆，最大堆的性质是父节点的值总是大于其左右子节点的值，那么此时根节点的值是最大的，则将其移到序列的最右边。之后将堆中当前最后一个叶节点移到根节点上，因为这可能会不符合最大堆的性质，所以会进行调整，将它与其左右子节点中最大的值进行交换，则相当于将叶节点向下移动，交换过后如果还是不符合性质，则继续进行交换，直到符合性质后，此时的根节点的值就是当前堆中的最大值，将其取出放入序列中正确的位置后继续上述流程处理剩下的节点。
globallength2


defheapify(arr,i):
left=2*i+1
right=2*i+2
largest=i
ifleftarr[largest]:
largest=left
ifrightarr[largest]:
largest=right
iflargest!=i:
arr[i],arr[largest]=arr[largest],arr[i]
heapify(arr,largest)


defbuild_max_heap(arr):
foriinrange(len(arr)//2,-1,-1):
heapify(arr,i)


defheap_sort(arr):
globallength2
length2=len(arr)
build_max_heap(arr)
foriinrange(len(arr)-1,0,-1):
arr[0],arr[i]=arr[i],arr[0]
length2-=1
heapify(arr,0)
returnarr
计数排序


将序列中的元素按照其值放入相应的桶中，之后再按照桶的顺序取出即可，计数排序不需要比较操作。
defcounting_sort(arr):
max_value=max(arr)
buckets=[0]*(max_value+1)
index=0
length=len(arr)
foriinrange(length):
buckets[arr[i]]+=1
forjinrange(max_value+1):
whilebuckets[j]>0:
arr[index]=j
index+=1
buckets[j]-=1
returnarr

桶排序


类别计数排序，构造很多桶，但每个桶中能放入值在特定范围内的元素，将序列中的元素按照要求放入各个桶中，再将每个桶中的元素进行排序，最后按照桶的顺序和各个桶中元素的顺序得到最终序列。
defbucket_sort(arr):
bucket_size=5
max_value=max(arr)
min_value=min(arr)
bucket_num=(max_value-min_value)//bucket_size+1
buckets={i:[]foriinrange(bucket_num)}
foriinrange(len(arr)):
buckets[(arr[i]-min_value)//bucket_size].append(arr[i])
result=[]
foriinrange(bucket_num):
insertion_sort(buckets[i])
result.extend(buckets[i])
returnresult

基数排序


按照元素值的特定位进行排序，从低位到高位分别进行排序。
defradix_sort(arr):
max_value=max(arr)
max_digit=len(str(max_value))
dev=1
mod=10
result=arr[:]
foriinrange(max_digit):
buckets={i:[]foriinrange(mod)}
forkinrange(len(result)):
key=(result[k]%mod)//dev
buckets[key].append(result[k])
result=[]
forjinrange(mod):
result.extend(buckets[j])
dev*=10
mod*=10
returnresult

上述代码放在这里
参考



https://www.cnblogs.com/onepixel/p/7674659.html
算法导论
菜鸟教程

到此这篇关于python实现经典排序算法的示例代码的文章就介绍到这了,更多相关python经典排序算法内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

python实现经典排序算法的示例代码

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

计数排序

桶排序

基数排序

参考

热门推荐

随机推荐