排序 | 笔记整理!

import numpy as np

def quick_sort(nums,l,r):
    if l>=r:
        return 
    # 稍微进行优化!
    rand=l+np.random.randint(100)%(r-l+1)
    nums[l],nums[rand]=nums[rand],nums[l]
    x=nums[l]
    i,j=l,r
    while i<j:
        while i<j and nums[j]>x:j-=1
        if i<j:
            nums[i]=nums[j]
            i+=1
        
        while i<j and nums[i]<x:i+=1
        if i<j:
            nums[j]=nums[i]
            j-=1
    nums[i]=x
    quick_sort(nums,l,i-1)
    quick_sort(nums,i+1,r)

if __name__=='__main__':
    nums=np.random.randint(100,size=12)
    print("生成的数组是:",nums)
    quick_sort(nums,0,11)
    print("排序后数组是:",nums)

import numpy as np

def merge_sort(nums,l,r):
    if l>=r:
        return 

    mid=l+r>>1
    # 对于 l~mid 和 mid+1~r 进行分别处理
    merge_sort(nums,l,mid)
    merge_sort(nums,mid+1,r)

    # 此处已经是 处理之后的 结果.进行归并即可!
    i,j=l,mid+1
    idx=0
    while i<=mid and j<=r:
        if nums[i]<=nums[j]:
            help_ls[idx]=nums[i]
            i+=1
        else:
            help_ls[idx]=nums[j]
            j+=1
        idx+=1
    while i<=mid:
        help_ls[idx]=nums[i]
        i+=1
        idx+=1

    while j<=r:
        help_ls[idx]=nums[j]
        j+=1
        idx+=1
    # 进行复制即可
    for i in range(idx): 
        nums[l+i]=help_ls[i]
if __name__=='__main__':
    n=12
    nums=np.random.randint(100,size=n)
    help_ls=[0]*n  # 生成辅助数组

    print("生成的数组是:",nums)
    merge_sort(nums,0,11)
    print("排序后数组是:",nums)

import numpy as np

def counting_sort(nums):
    # 进行计数
    for i in nums:
        help_c[i]+=1

    # 输出结果
    print("排序后数组是:",end=' ')
    for i in range(max_val):
        for j in range(help_c[i]): #需要重复的次数是
            print(i,end=' ')
    # 前缀和
    for i in range(1,max_val):
        help_c[i]+=help_c[i-1]

    for i in range(n-1,-1,-1):
        help_r[i]=help_c[nums[i]]
        help_c[nums[i]]-=1

    print("\n出现的次序:",end=' ')
    for i in range(n):
        print(help_r[i],end=' ')
if __name__=='__main__':
    n=12
    max_val=10
    nums=np.random.randint(max_val,size=n)
    help_a=[0]*n  # 生成辅助数组
    help_c=[0]*n  # 生成辅助数组
    help_r=[0]*n  # 生成辅助数组
    print("生成的数组是:",nums)
    counting_sort(nums)

import numpy as np
def counting_sort():
    help_c=[0]*10  # 生成辅助数组

    # 进行计数即可
    for i in help_v:
        help_c[i]+=1
    # 前缀和
    for i in range(1,10):
        help_c[i]+=help_c[i-1]
    # 从后开始 这是用help_s用来标记位次顺序
    for i in range(n-1,-1,-1):
        help_r[help_s[i]]=help_c[help_v[help_s[i]]]
        help_c[help_v[help_s[i]]]-=1
    # 记录这次之后的位次顺序 因为是从0开始的 位次是1
    for i in range(n):
        help_s[help_r[i]-1]=i
if __name__=='__main__':
    n=12
    max_val=100
    nums=np.random.randint(max_val,size=n)
    help_s=list(range(n))
    help_r=[0]*n  # 生成辅助数组
    help_v=[0]*n  # 生成辅助数
    x=1
    print("生成的数组是:",list(nums))
    for i in range(2):
        for j in range(n):
            help_v[j]=nums[j]//x%10 
        counting_sort()
        x*=10
    print("排序后数组是:",[nums[help_s[i]] for i in range(n)])