import math
#1.冒泡排序
def bubbleSort(arr):
    for i in range(1,len(arr)):
        for j in range(0,len(arr)-i):
            if(arr[j]>arr[j+1]):
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr

#2.选择排序
def selectionSort(arr):
    for i in range(len(arr)-1):
        minindex=i
        for j in range(i+1,len(arr)):
            if arr[j]<arr[minindex]:
                minindex=j
        if i!=minindex:
            arr[i],arr[minindex]=arr[minindex],arr[i]
    return arr


#3.插入排序
def insertionSort(arr):
    for i in range(len(arr)):
        preindex=i-1
        current=arr[i]
        while preindex>=0 and arr[preindex]>current:
            arr[preindex+1]=arr[preindex]
            preindex-=1
        arr[preindex+1]=current
    return arr

#4.希尔排序
def shellSort(arr):
    gap=1
    while(gap<len(arr)/3):
        gap=gap*3+1
    while gap>0:
        for i in range(gap,len(arr)):
            temp=arr[i]
            j=i-gap
            while j>=0 and arr[j]>temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap]=temp
        gap=math.floor(gap/3)
    return arr


#5.归并排序
def mergeSort(arr):
    if(len(arr)<2):
        return arr
    result=[]
    middle=math.floor(len(arr)/2)
    left,right=arr[0:middle],arr[middle:]
    while len(left) and len(right):
        if(left[0]<=right[0]):
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


#6.快速排序
def quickSort(arr,left=None,right=None):
    left=0 if not isinstance(left,(int,float)) else left
    right=len(arr)-1 if not isinstance(right,(int,float)) else right
    if(left<right):
        partitionindex=partition(arr,left,right)
        quickSort(arr,left,partitionindex-1)
        quickSort(arr,partitionindex+1,right)
    return arr


def partition(arr,left,right):
    pivot=left
    index=pivot+1
    i=index
    while i<=right:
        if(arr[i]<arr[pivot]):
            arr[i],arr[index]=arr[index],arr[i]
            index+=1
        i+=1
    arr[pivot],arr[index-1]=arr[index-1],arr[pivot]
    return index-1

#7.堆排序
def buildmaxHeap(arr):
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr,i):
    left=2*i+1
    right=2*i+2
    largest=i
    if(left<arrlen and arr[left]>arr[largest]):
        largest=left
    if(right<arrlen and arr[right]>arr[largest]):
        largest=right
    if(largest!=i):
        arr[i],arr[largest]=arr[largest],arr[i]
        heapify(arr,largest)

def heapSort(arr):
    global arrlen
    arrlen=len(arr)
    buildmaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        arr[0],arr[i]=arr[i],arr[0]
        arrlen-=1
        heapify(arr,0)
    return arr


#8.计数排序
def countingSort(arr):
    bucketlen=max(arr)+1
    bucket=[0]*bucketlen
    sortedindex=0
    for i in range(len(arr)):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketlen):
        while(bucket[j]>0):
            arr[sortedindex]=j
            sortedindex+=1
            bucket[j]-=1
    return arr


#9.桶排序
def bucketSort(arr):
    minnum=min(arr)
    maxnum=max(arr)
    bucketnum=(maxnum-minnum)/len(arr)
    count_list=[[] for i in range(len(arr)+1)]
    for i in arr:
        count_list[int((i-minnum)//bucketnum)].append(i)
    arr.clear()
    for i in count_list:
        for j in sorted(i):
            arr.append(