ソートアルゴリズムpython 3バブル選択挿入ヒル集計高速スタックソートカウントバケツソート基数ソート

def mp_sort(arr):
    '''
        
    '''
    for i in range(0,len(arr)-1):
        for j in range(0,len(arr)-1-i):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]

def sel_sort(arr):
    '''
        
    '''
    for i in range(0,len(arr)-1):
        x,min_ = i,arr[i]
        for j in range(i+1,len(arr)):
            if arr[j] < min_:
                x = j
                min_ = arr[j]
        arr[i],arr[x] = arr[x],arr[i]

def insert_sort(arr):
    '''
        
    '''
    for i in range(1,len(arr)):
        val = arr[i]
        j = i-1
        while j > -1 and val <= arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = val

def shell_sort(arr):
    '''
        
    '''
    #        
    a,shell = len(arr),[]
    while a > 1:
        a //= 2
        shell.append(a)
    #print(shell)
    #i  shell  
    for i in shell:
        #j         
        for j in range(i,len(arr)):
            val = arr[j]
            k = j-i  #k        
            while k > -1 and val < arr[k]:
                arr[k+i] = arr[k]
                k -= i
            arr[k+i] = val
        print(f'{i}     :{arr}')

def Merge_sort(arr):
    '''
        ，  
    '''
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = Merge_sort(arr[:mid])
    right = Merge_sort(arr[mid:])
    return merge(left,right)

def merge(left,right):
    '''
             
    '''
    #print(f'   left{left},right:{right}')

    a = []
    while len(left)>0 and len(right)>0:
        if left[0] < right[0]:
            a.append(left.pop(0))
        else:
            a.append(right.pop(0))

    if len(left) > 0:
        a.extend(left)

    if len(right) > 0:
        a.extend(right)

    #print(f'a  :',a)
    return a

def quick_sort(arr):
    '''
        ,  
    '''
    #          ，           a[0]  ，left  []
    if len(arr) <= 1:
        return arr
    a = arr[0]
    left,right = [],[]
    for i in range(1,len(arr)):
        if arr[i] > a:
            right.append(arr[i])
        else:
            left.append(arr[i])
    return quick_sort(left) + [a] + quick_sort(right)

def quick_sort2(arr):
    '''
        ，  
    '''
    if len(arr) <= 1:
        return arr
    mid = 0
    i = 0
    while i < len(arr):
        if arr[i] < arr[mid] and i > mid:
            arr[i],arr[mid] = arr[mid],arr[i]
            mid,i = i,mid
        if arr[i] > arr[mid] and i < mid:
            arr[i],arr[mid] = arr[mid],arr[i]
            mid,i = i,mid
        i += 1
    print(f'    :{arr[:mid]},  :{arr[mid]},  :{arr[mid+1:]}')
    return quick_sort2(arr[:mid]) + [arr[mid]] + quick_sort2(arr[mid+1:])

def heapify(arr,n,i):
    '''
       
    '''
    largest = i
    l = 2*i + 1
    r = 2*i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]

        heapify(arr,n,largest)

def heapSort(arr):
    '''
       
    '''
    n = len(arr)

    #     
    for i in range(n,-1,-1):
        heapify(arr,n,i)

    #                   ，                ，       ,  ，       ，        
    for i in range(n-1,0,-1):
        arr[i],arr[0] = arr[0],arr[i]
        heapify(arr,i,0)

def count_sort(arr):
    '''
        
    '''
    min_,max_ = min(arr),max(arr)
    base = max_ - min_ + 1 #          
    temp = [0 for i in range(base)]
    #     l    
    for i in arr:
        temp[i-min_] += 1
    #     
    rel = []
    for i in range(len(temp)):
        while temp[i] > 0:
            rel.append(i+min_)
            temp[i] -= 1
    return rel

def BucketSort(arr):
    '''
       
    '''
    min_,max_ = min(arr),max(arr)
    base = 5
    index_base = max_//5
    #     ，   5    ，        
    a = [[] for i in range(base+1)]
    for i in arr:
        a[i//index_base].append(i)

    #             ，           
    for i in range(len(a)):
        if len(a[i]) <= 1:
            continue
        a[i] = count_sort(a[i])
    #     
    print(f'        :{a}')
    #     ，        
    rel = []
    for i in a:
        rel.extend(i)

    return rel

def RadixSort(arr):
    '''
        
    '''
    max_ = max(arr)
    max_bit = len(str(max_)) #         
    radix = arr #           s   
    temp = [[] for i in range(10)] #    s 

    for i in range(max_bit):
        #       (     ，   ,  temp
        for j in radix:
            a = j//10**i % 10
            temp[a].append(j)
        #        ，  radix 
        radix = [] #     
        for k in temp:
            radix.extend(k)
        temp = [[] for i in range(10)] #    
        print(f' {i}  ，     :{radix}')
    return radix