排序

warning: 这篇文章距离上次修改已过1006天,其中的内容可能已经有所变动。

桶排序:
桶排序的思想:数组x的下标是有序的,例如x[0],x[1],x[2]中的0,1,2;
桶排序的要旨是把待排序的数据放到数组x中,根据x中的最大值m设置数组y[0]->y[m]=0;
循环遍历x数组i in range(m+1)次,如果x[j]=i,那么y[x]=y[x]+1
现在x中的元素变成了数组y中的下标中值不为0的下标

def bucket_sort():
    import random
    x,y=[],[]
    for i in range(20):         #用random函数随机生成一组数据放到数组x中
        a=random.randint(0,12)
        x.append(a)
    print("x中的原数据:",x)
    m=max(x)                    #找出x中的最大值m,m决定了数组y的长度
    print("数组x中的最大值:",m)
    for i in range(0,m+1):     #数组y的长度为m+1,并赋值为0
        y.append(0)
    for i in range(20):
        y[x[i]]+=1
    print("y中的值",y)
    for i in range(m+1):
        for j in range(0,y[i]):
            print(i,end=' ')
bucket_sort()

冒泡排序:

def bubble_sort():
    import random
    x=[]
    m=eval(input("输入随机生成数据的个数:"))
    for i in range(m):
        a=random.randint(0,20)   #随机生成数的大小范围
        x.append(a)
    print("数组x中的数据:",x)
    for i in range(1,len(x)):
        for j in range(0,len(x)-i):
            if x[j]<x[j+1]:
                x[j],x[j+1]=x[j+1],x[j]
    print("排序后:",x)
bubble_sort()

快速排序:

def Quick_sort(lists:list,left:int,right:int):
    # 跳出递归判断
    if left>=right:
        return lists
    # 选择参考点,该调整范围的第1个值
    key=lists[left]
    low=left
    high=right
    # 循环判断直到遍历全部
    while left<right:
        # 从右边开始查找大于参考点的值
        while left<right and key<=lists[right]:
            right-=1
        lists[left]=lists[right]  # 这个位置的值先挪到左边
        # 从左边开始查找小于参考点的值
        
        while left<right and key>=lists[left]:
            left+=1
        lists[right]=lists[left]  # 这个位置的值挪到右边
        
    # 写回改成的值
    lists[left]=key
    
    # 递归,并返回结果
    Quick_sort(lists,low,left-1)  # 递归左边部分
    Quick_sort(lists,left+1,high) # 递归右边部分
    return lists

lists=[4,5,3,8,6,2,7,9,4,1]
Quick_sort(lists,0,len(lists)-1)
print(lists)

添加新评论