面试常考排序算法汇总（Python版）

面试常考排序算法汇总（Python版）

快速排序

def qiuckSort(nums,left,right):
    if left >= right: return
    randomNum=nums[right]
    print(randomNum)
    i,j=left,right
    while(i<j):
        while i<j and nums[i]<randomNum:
            i+=1
        nums[j]=nums[i]
        while i<j and nums[j]>=randomNum:
            j-=1
        nums[i]=nums[j]
    nums[i]=randomNum
    qiuckSort(nums,left,i-1)
    qiuckSort(nums,i+1,right)
nums=[5,6,8,4,2,1,15]
print("排序前：",nums)
qiuckSort(nums,0,len(nums)-1)
print("排序后：",nums)

堆排序

堆排序借用了完全二叉树的数据结构，在排序过程中使得每个节点的数值都要大于左右孩子的数值：

#n表示排序长度，i表示要构建最大堆的节点
def buildHeap(nums,n,i):
    lagest=i
    left=2*i+1
    right=2*i+2
    if left<n and nums[left]>nums[lagest]:
        lagest=left
    if right<n and nums[right]>nums[lagest]:
        lagest=right
    if lagest!=i:
        nums[lagest],nums[i]=nums[i],nums[lagest]
        buildHeap(nums,n,lagest)
def heapSort(nums):
    n=len(nums)
    for i in range(n,-1,-1):
        buildHeap(nums,n,i)
    for i in range(n-1,0,-1):
        nums[i],nums[0]=nums[0],nums[i]
        buildHeap(nums,i,0)
a=[3,6,8,1,10,5,5,8,20]
heapSort(a)

归并排序

def Merge(leftList,rightList):
    tmpList=[]
    i=0
    j=0
    while i<len(leftList) and j<len(rightList):
        
        if leftList[i]<=rightList[j]:
            tmpList.append(leftList[i])
            i+=1
        else:
            tmpList.append(rightList[j])
            j+=1
    if j==len(rightList):
        for k in leftList[i:]:
            tmpList.append(k)
    else:
        for k in rightList[j:]:
            tmpList.append(k)
    return tmpList

def MergeSort(my_list):
    if len(my_list)<=1:
        return my_list
    middle=int(len(my_list)/2)
    left=MergeSort(my_list[:middle])
    right=MergeSort(my_list[middle:])
    
    return Merge(left,right)

if __name__=='__main__':
    TestList=[5,8,24,1,44,0]

基数排序

def Sort(nums):
    maxNum=max(nums)
    exp=1
    while(exp <= maxNum):
        cont=dict()
        for i in range(10):
            cont[i]=list()
        for i in nums:
            index=int(i / exp) % 10
            cont[index].append(i)
        nums=[]
        for i in range(10):
            if len(cont[i]):
                nums.extend(cont[i])
        exp=10*exp
    return nums
nums=[5,6,8,4,2,1,15]
print("排序前：",nums)
nums=Sort(nums)
print("排序后：",nums)

记录一下！