前言

本文记录了我在学习《图解LeetCode初级算法（Python版）》中的六大排序.若有不足，请多指教.
由于很多小伙伴在大学学到排序算法是用C语言写的，对我个人而言Python版本会更容易理解排序的思想。
本文适合对于各个排序算法有一定基础概念的同学阅读，对于不太熟悉基本排序算法的同学建议可以找一些排序算法的动画来看看。接下来就直接 "Show me the Code"

随机数组

这一段程序主要用于创建无序数列；用于测试排序算法。可以新建一个本地文件，存储这段代码,文件名称为
randomList.py

import random
def randomList(n):
    iList = [];
    for i in range(n):
        iList.append(random.randrange(1000))
    return iList
if __name__ == "__main__":
    iList = randomList(10)
    print(iList)

冒泡排序

from randomList import randomList
import timeit
iList = randomList(20)

def bubbleSort(iList):
    ''' 冒泡排序'''
    if len(iList) <=1:
        return iList
    for i in range(1,len(iList)):
        for j in range(0,len(iList)-1):
            if iList[j] >= iList[j+1]: #比较相邻两数大小
                iList[j] , iList[j+1] = iList[j+1], iList[j]
        #print("第 %d 轮排序结果:", end = "")
        #print(iList)
    return iList
if __name__ == "__main__":
    print(iList)
    print(bubbleSort(iList))
    print(timeit.timeit("bubbleSort(iList)", "from __main__ import bubbleSort,iList", number =100))

插入排序

from randomList import randomList
import timeit
iList = randomList(20)

def insertionSort(iList):
    if len(iList)<=1:
        return iList
    #把未排序的数组分成左边跟右边。
    for right in range(1,len(iList)):
        #limit是边界的那个数字
        limit = iList[right]
        for left in range (0, limit):
            #如果边界的数字比left小，把left及其后面的整块往后移，
            #然后left就是该插入的位置，一直调整到limit在左边是最小的
            #这一段比较抽象，有需要的话建议拿纸笔一步步推导看看.
            if limit <= iList[left]:
                #使用python的切片赋值
                #直接切块赋值之后会有一个left是重复的
                #直接赋值的时候，被覆盖掉的那个数字就是limit
                #再把limit放入其中。
                iList[left+1:right+1] = iList[left:right]
                iList[left] =limit
                break
        return iList
if __name__ == "__main__":
    print(iList)
    print(insertionSort(iList))
    print(timeit.timeit("insertionSort(iList)", "from __main__ import insertionSort,iList", number = 100))            

选择排序

from randomList import randomList
import timeit
iList = randomList(20)

def selectionSort(iList):
    if len(iList) <=1:
        return iList
    for i in range (0, len(iList)-1):
        if iList[i] != min(iList[i:]):
            minIndex = iList.index(min(iList[i:]))
            iList[i] , iList[minIndex] = iList[minIndex] , iList[i]
        #print("第 %d 轮的排序结果:" %(i+1), end="")
        #print(iList)
    return iList
if __name__ == "__main__":
    print(iList)
    print(selectionSort(iList))
    print(timeit.timeit("selectionSort(iList)", "from __main__ import selectionSort,iList", number = 100))

归并排序

from randomList import randomList
import timeit
iList = randomList(20)

def mergeSort(iList):
    if len(iList)<=1:
        return iList
    middle = len(iList)//2  #将数组分成左右两部分
    left, right = iList[0:middle], iList[middle:] #相当于不断地把数组二分
    return mergeList(mergeSort(left), mergeSort(right)) #再分别对左右两部分别进行排序 
def mergeList(left,right):
    mList = []
    while left and right:
        #当左右两个小数组都存在时，把小的放入mlist，
        if left[0] >= right[0]:
            mList.append(right.pop(0))
        else:
            mList.append(left.pop(0))
    #只有单边存在时就直接放入。
    while left:
        mList.append(left.pop(0))
    while right:
        mList.append(right.pop(0))
    return mList
if __name__ == "__main__":
    print(iList)
    print(mergeSort(iList))
    print(timeit.timeit("mergeSort(iList)", "from __main__ import mergeSort,iList", number = 100))

快速排序

from randomList import randomList
import timeit
iList = randomList(20)

def quickSort(iList):
    if len(iList) <=1:
        return iList
    left =[]
    right = []
    #设置iList[0]为参考点，若小于它则放在左边，否则放右边
    for i in iList[1:]:
        if i<=iList[0]:
            left.append(i)
        else:
            right.append(i)
            #左边的left数组会被当作新的数组进行quickSort,右边也是，最后合并成有序数组
            #合并的时候必须是数列才能相互合并，因此需要将iList[0]列表化
    return quickSort(left) + [iList[0]] + quickSort(right)
if __name__ == "__main__":
    print(iList)
    print(quickSort(iList))
    print(timeit.timeit("quickSort(iList)", "from __main__ import quickSort,iList", number = 100))

计数排序

from randomList import randomList
import timeit
iList = randomList(20)

def countingSort(iList):
    if len(iList) <=1:
        return iList
    iLen = len(iList)
    #首先创造相同长度的空数组.
    rList = [None] *iLen 
    #便利整个数组，如果比x小的有4个，那么x就放在第五位。
    for i in range(iLen):
        #注意small, same 的位置，需要重置.
        small = 0 #比基数小的
        same =0 #比基数相等的
        for j in range(iLen):
            if iList[j] < iList[i]:#有多少个比较小
                small+=1
            elif iList[j] == iList[i]: #相同的数字
                same +=1
        for k in range(small, small+same):
            #前面加入有5个比较小，就放在第六位，
            #如果有3个数字一样，就第六、七、八这三个位置放一样的数.
            rList[k] = iList[i]
    return rList

if __name__ == "__main__":
    print(iList)
    print(countingSort(iList))
    print(timeit.timeit("countingSort(iList)", "from __main__ import countingSort,iList", number = 100))

总结

1. 冒泡排序、选择排序、插入排序的时间复杂度都是
2. 归并排序的时间复杂度为
3. 快速排序最快的情况下时间复杂度为 , 最好情况是
4. 选择排序在Python下算法时间复杂度是,因为Python中的min函数可以一步到位地获取列表最小值.
5. 计数排序的时间复杂度是,其中k是数列中整数的范围.
6. 堆排序、希尔排序、基数排序......未来再继续更新.
7. 觉得有用记得点赞❤️.