【python练习】三种排序算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【python练习】三种排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

排序算法
Description

试用选择算法或冒泡算法或快速排序算法对一列数进行升序排列。

如：

9 9 1 4 10 2 1 8 7 4

排列后为：

1 1 2 4 4 7 8 9 9 10


Input
一列若干个整数


Output
排序后的一列整数


Sample Input 1 

9 9 1 4 10 2 1 8 7 4
Sample Output 1

1 1 2 4 4 7 8 9 9 10
Hint

本题主要练习各种排序算法。如果只是为了AC，当然只用内置sorted函数即可。

Source

中学生可以这样学Python，P190-P193例8-21，例8-22，例8-23

冒泡排序

#冒泡排序，每个元素，都跟相邻元素比大小，一直比到最后一个
a=list(map(int,input().split()))
for i in range(len(a)-1):
    #print(a[i])
    for j in range(i+1,len(a)):
        if a[i]>a[j]:
            a[i],a[j]=a[j],a[i]
print(*a)

测试时候有两个节点超时

选择排序

#选择排序，每次扫描剩余数中最大值或最小值与当前位置数交换
a=list(map(int,input().split()))
for i in range(len(a)-1):
    small=min(a[i+1:])
    index=a[i+1:].index(small)+i+1
    if a[i]>a[index]:
        a[i],a[index]=a[index],a[i]
print(*a)

a=list(map(int,input().split()))
for i in range(len(a)-1):
    k=i
    for j in range(i+1,len(a)):
        if a[j]<a[k]:
            k=j
    if i!=k:
        a[i],a[k]=a[k],a[i]
print(a)

测试时候有两个节点超时

快速排序

a=list(map(int,input().split()))

def kuaisu(a,l,r):
    if l>=r:
        return
    i=l
    j=r
    p=a[l]
    while i<j:
        while i<j and a[j]>=p:
            j=j-1
        a[i]=a[j]
        while i<j and a[i]<=p:
            i=i+1
        a[j]=a[i]
        #a[i],a[j]=a[j],a[i]
    a[i]=p
    kuaisu(a,l,i-1)
    kuaisu(a,i+1,r)
kuaisu(a,0,len(a)-1)
print(*a)

上面仿照书本上的快速排序，但没太看懂，根据这个视频【Python小知识】星途文化_python19：快速排序的概念和实现学了一个不太一样的，迷惑

#快速排序，每次选一个数，以此为分界点将元素分成两部分，前面的比该元素小，后面的比该元素大，重复，直到排好
a=list(map(int,input().split()))
def kuaisu(alist):
    if len(alist)<=1:
        return alist
    p=alist[len(alist)//2]
    left=[x for x in alist if x<p]
    mid=[x for x in alist if x==p]
    right=[x for x in alist if x>p]
    return kuaisu(left)+mid+kuaisu(right)
print(*kuaisu(a))

通过测试文章来源地址https://www.toymoban.com/news/detail-714272.html

到了这里，关于【python练习】三种排序算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！