十大經典排序演算法

資料結構中的十大經典演算法：冒泡排序、快速排序、簡單插入排序、希爾排序、簡單選擇排序、堆排序、歸并排序、計數排序、桶排序、基數排序

十大經典演算法的復雜度和穩定性（如果a原本在b前面，而a=b，排序之后a仍然在b的前面）：

一、交換排序

1、冒泡排序（前后比較-交換）

（1）演算法思想

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成

（2）python實作代碼

def bubble_sort(blist):
    count = len(blist)
    for i in range(0, count):
        for j in range(i + 1, count):
            if blist[i] > blist[j]:
                blist[i], blist[j] = blist[j], blist[i]
    return blist

2、快速排序（選取一個基準值，小數在左大數在右）

（1）演算法思想

找基準數，通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列

（2）python實作代碼

def quick_sort(qlist):
    if qlist == []:
        return []
    else:
        qfirst = qlist[0]
        qless = quick_sort([l for l in qlist[1:] if l < qfirst])
        qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
        return qless + [qfirst] + qmore

二、插入排序

1、簡單插入排序（逐個插入到前面的有序數中）

（1）演算法思想

插入排序的基本操作就是將一個資料插入到已經排好序的有序資料中，從而得到一個新的、個數加一的有序資料，演算法適用于少量資料的排序；首先將第一個作為已經排好序的，然后每次從后的取出插入到前面并排序

（2）python實作代碼

def insert_sort(ilist):
    for i in range(len(ilist)):
        for j in range(i):
            if ilist[i] < ilist[j]:
                ilist.insert(j, ilist.pop(i))
                break
    return ilist

2、希爾排序（從大范圍到小范圍進行比較-交換）

（1）演算法思想

先取一個正整數 d1，以 d1 間隔分組，先對每個分組內的元素使用插入排序操作，重復上述分組和直接插入排序操作；直至 di = 1，即所有記錄放進一個組中排序為止，

（2）python實作代碼

def shell_sort(slist):
    gap = len(slist)
    while gap > 1:
        gap = gap // 2
        for i in range(gap, len(slist)):
            for j in range(i % gap, i, gap):
                if slist[i] < slist[j]:
                    slist[i], slist[j] = slist[j], slist[i]
    return slist

三、選擇排序

1、簡單選擇排序（選擇最小的資料放在前面）

（1）演算法思想

第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢

（2）python實作代碼

def select_sort(slist):
    for i in range(len(slist) - 1):
        x = i
        for j in range(i, len(slist)):
            if slist[j] < slist[x]:
                x = j
        slist[i], slist[x] = slist[x], slist[i]
    return slist

2、堆排序（利用最大堆和最小堆的特性）

（1）演算法思想

它是選擇排序的一種，可以利用陣列的特點快速定位指定索引的元素，堆分為大根堆和小根堆，是完全二叉樹，大根堆的要求是每個節點的值都不大于其父節點的值，在陣列的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂

（2）python實作代碼

import math
 
def heap_sort(a):
    al = len(a)
 
    def heapify(a, i):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < al and a[left] > a[largest]:
            largest = left
        if right < al and a[right] > a[largest]:
            largest = right
 
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(a, largest)
 
    # 建堆
    for i in range(math.floor(len(a) / 2), -1, -1):
        heapify(a, i)
 
    # 不斷調整堆：根與最后一個元素
    for i in range(len(a) - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        al -= 1
        heapify(a, 0)
    return a

四、歸并排序

（1）演算法思想

采用分治法（Divide and Conquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并

（2）python實作代碼

def merge_sort(a):
    if(len(a)<2):
        return a
    middle = len(a)//2
    left, right = a[0:middle], a[middle:]
    return merge(merge_sort(left), merge_sort(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

五、其他排序

1、計數排序（字典計數-還原）

（1）演算法思想

計數排序的核心在于將輸入的資料值轉化為鍵存盤在額外開辟的陣列空間中，作為一種線性時間復雜度的排序，計數排序要求輸入的資料必須是有確定范圍的整數，

（2）python實作代碼

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        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

2、桶排序（鏈表）

（1）演算法思想

為了節省空間和時間，我們需要指定要排序的資料中最小以及最大的數字的值，將陣列分到有限數量的桶子里，每個桶子再個別排序（有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排序）

（2）python實作代碼

def bucketSort(nums):
    bucket=[0]*(max(nums)-min(nums)+1)
    for i in range(len(nums)):
        bucket[nums[i]-min(nums)]+=1
    tmp=[]
    for i in range(len(bucket)):
        if bucket[i]!=0:
            tmp+=[min(nums)+i]*bucket[i]
    return tmp

3、基數排序

（1）演算法思想

基數排序將資料按位進行分桶，然后將桶中的資料合并，每次分桶只關注其中一位資料，其他位的資料不管，最大的資料有多少位，就進行多少次分桶和合并，由于整數也可以表達字串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數，

（2）python實作代碼

def radix_sort(array):
    bucket, digit = [[]], 0
    while len(bucket[0]) != len(array):
        bucket = [[], [], [], [], [], [], [], [], [], []]
        for i in range(len(array)):
            num = (array[i] // 10 ** digit) % 10
            bucket[num].append(array[i])
        array.clear()
        for i in range(len(bucket)):
            array += bucket[i]
        digit += 1
    return array