參考：https://sort.hust.cc/

0x01 冒泡排序

原理
比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。 對(duì)每一對(duì)相鄰元素做同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。 針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。

實(shí)現(xiàn)代碼

def bubblesort(nums):
    for i in range(1,len(nums)):
        for j in range(0,len(nums)-i):
            if nums[j] > nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
    return nums

print(bubblesort([2,3,1,5,4,7,0,8,0]))

0x02 選擇排序

原理
第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰?，然后放到已排序的序列的末尾。以此?lèi)推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

實(shí)現(xiàn)代碼

def selectsort(nums):
    for i in range(len(nums)-1):
        for j in range(i+1,len(nums)):
            if nums[i] > nums[j]:
                nums[i],nums[j] = nums[j],nums[i]
    return nums

print(selectsort([3,2,1,5,7,6,9,0]))

0x03 插入排序

原理
從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。

實(shí)現(xiàn)代碼

def insertionsort(nums):
    for i in range(len(nums)):
        a = i-1
        index = nums[i]
        while a >= 0 and nums[a] > index:
            nums[a+1] = nums[a]
            a -= 1
        nums[a+1] = index
    return nums

print(insertionsort([2,3,4,1,7,6,0,9,8,5]))

0x04 希爾排序

原理
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
一種特殊的插入排序

實(shí)現(xiàn)代碼

def shellsort(nums):
    import math
    gap = 1
    while(gap < len(nums)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(nums)):
            temp = nums[i]
            j = i-gap
            while j>=0 and nums[j] > temp:
                nums[j+gap] = nums[j]
                j-=gap
            nums[j+gap] = temp
        gap = int(math.floor(gap/3))
    return nums

print(shellsort([3,2,1,4,5,7,6,9,0,8]))

0x05 歸并排序

原理
已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。

實(shí)現(xiàn)代碼

def mergesort(nums):
    import math
    if len(nums) < 2:
        return nums
    middle = int(math.floor(len(nums)/2))
    left,right = nums[0:middle],nums[middle:]
    return merge(mergesort(left),mergesort(right))

def merge(left,right):
    result = []
    while left and 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

print(mergesort([5,4,3,2,1,6,8,0,9,7]))

0x06 快速排序

原理
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

一趟快速排序的算法是:
(1)設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；
(2)以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
(3)從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換；
(4)從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]的值交換；
(5)重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）

實(shí)現(xiàn)代碼

def quicksort(nums):
    if len(nums) >= 2:
        middle = nums[(len(nums)//2)]
        left = []
        right = []
        nums.remove(middle)
        for num in nums:
            if num > middle:
                right.append(num)
            else:
                left.append(num)
        return quicksort(left)+[middle]+quicksort(right)
    else:
        return nums

print(quicksort([3,2,1,6,5,4,9,7,0,8]))

0x07 堆排序

原理
利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，一種選擇排序

(1)根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個(gè)完全二叉樹(shù)，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）；
(2)每次交換第一個(gè)和最后一個(gè)元素，輸出最后一個(gè)元素（最大值），然后把剩下元素重新調(diào)整為大根堆；
(3)循環(huán)第二步，直到當(dāng)輸出完最后一個(gè)元素。

實(shí)現(xiàn)代碼

def buildmaxheap(nums):
    import math
    for i in range(int(math.floor(len(nums)/2)),-1,-1):
        heapify(nums,i)

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

    if largest != i:
        swap(nums,i,largest)
        heapify(nums,largest)

def swap(nums,i,j):
    nums[i],nums[j] = nums[j],nums[i]

def heapsort(nums):
    global numslen
    numslen = len(nums)
    buildmaxheap(nums)
    for i in range(len(nums)-1,0,-1):
        swap(nums,0,i)
        numslen -=1
        heapify(nums,0)
    return nums

print(heapsort([9,2,3,1,4,5,6,8,0,7]))

0x08 計(jì)數(shù)排序

原理
對(duì)于給定的輸入序列中的每一個(gè)元素x，確定該序列中值小于等于x的元素的個(gè)數(shù)（此處并非比較各元素的大小，而是通過(guò)對(duì)元素值的計(jì)數(shù)和計(jì)數(shù)值的累加來(lái)確定）。一旦有了這個(gè)信息，就可以將x直接存放到最終的輸出序列的正確位置上。

實(shí)現(xiàn)代碼

def countsort(nums):
    lennums = len(nums)
    nums2 = [None]*lennums
    for i in range(lennums):
        p = 0
        q = 0
        for j in range(lennums):
            if nums[i] > nums[j]:
                p += 1
            elif nums[i] == nums[j]:
                q += 1
        for k in range(p,p+q):
            nums2[k] = nums[i]
    return nums2

print(countsort([1,3,2,4,5,6,8,7,3,5]))

0x09 桶排序

原理
數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。

每個(gè)桶相差為1更方便

實(shí)現(xiàn)代碼

def bucketsort(nums):
    max_num = max(nums)
    bucket = [0]*(max_num+1)
    sort = []
    for i in nums:
        bucket[i] += 1
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for k in range(bucket[j]):
                sort.append(j)
    return sort

print(bucketsort([3,2,2,1,0,3,4,7,5,7,6]))

0x10 基數(shù)排序

原理
將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

1、首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中；
2、接下來(lái)將這些桶子中的數(shù)值按照個(gè)位數(shù)數(shù)值重新串接起來(lái)；
3、再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來(lái)分配；
4、接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái)；
5、重復(fù)分配與串聯(lián)操作，直到最高位為空。

實(shí)現(xiàn)代碼

def radixsort(nums):
    i = 0
    max_num = max(nums)
    j = len(str(max_num))
    while i < j:
        bucket = [[] for _ in range(10)]            #這里的_可以換成其他，但是不能用已出現(xiàn)的字符，會(huì)產(chǎn)生沖突
        print("test:",_)      #會(huì)輸出9
        for num in nums:
            bucket[int(num/(10**i))%10].append(num)
        nums = []
        for x in bucket:
            for y in x:
                nums.append(y)
        i += 1
    return nums

print(radixsort([22,1,4,34,76,67,54,48,0,90,78]))

• 桶排序VS計(jì)數(shù)排序VS基數(shù)排序

  桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值；
  計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值；
  基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶。