七大經典排序算法回顧python實作

大話資料結構這本書寫的非常好的一個地方就是，會将這個算法的全部原由通俗易懂的向你介紹，不會僅僅将注意力放在算法上傻傻的分析，而是通過有趣的背景，闡述算法的來源和意義，以此讓讀者達到深刻了解的目的，而不是僅僅“背”住了算法。覺得不能了解可以去多看看圖形和裡面的代碼執行個體。

插入類排序：簡單插入排序，更新為-希爾排序

選擇類排序：簡單選擇排序，更新為-堆排序

交換類排序：冒泡排序，更新為-快速排序

歸并排序：很多複雜的排序可以進行分塊解決。

桶排序：隻有特定資料類型可以，可以在O(n)時間完成排序，需要消耗部分桶空間。

代碼參考：https://blog.csdn.net/aiya_aiya_/article/details/79846380

'''冒泡排序
選擇理由：穩定，與原位置偏離不遠。
基本思想：正宗的冒泡排序，j其實從後往前走的，不過我們比較喜歡，
從下标0開始嘛，效果一樣，但是要知道。預設有增加一個狀态判斷。
時間複雜度：最差：O(n2),最好：O(n)
空間複雜度：O(1)
'''
def BublleSort(li):
    for i in range(len(li)):#定義幾趟排序n-1，最後一趟不比較
        for j in range(len(li)-i-1):#每趟排序的比較次數
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                
'''簡單選擇排序
選擇理由：穩定，很無序，與原位置偏離較遠。
基本思想:後面找到最小的值後再來交換，比冒泡排序的優點是
不用交換那麼多次。
時間複雜度：無論好差都是O(n2)
空間複雜度：O(1)
'''
def SelectSort(li):
    for i in range(len(li)-1):#定義趟數n-1
        minIndex = i
        for j in range(i+1,len(li)):#定義每趟排序的比較次數
            if li[minindex] > li[j]:
                minindex = j
        if minindex != i:
            li[i],li[minindex] = li[minindex],li[i]

'''簡單插入排序
選擇理由：穩定，基本有序。
基本思想:從第一個元素開始，不斷整理順序。
時間複雜度：最差：O(n2),最好：O(n)
空間複雜度：O(1)
'''
def InsertSort(li):
    for i in range(1, len(li)):#定義趟數n-1
        tempi = li[i]; j = i
        while j > 0 and tempi < li[j-1]:#for就顯示不出來優勢了
            li[j] = li[j-1]#後面的值上移
            j -= 1
        ls[j] = tempi

#前面三種都是O(n2)，經過後人的不斷努力，研究，速度才得以提升。排序要加快的基本原則之一，是讓後一次的排序進行時，盡量利用前一次排序後的結果，以加快排序的速度。

'''希爾排序-縮小增量排序
選擇理由：不穩定，适合基本無序的序列。簡單插入排序的更新！
基本思想:我們比較的元素可以再遠一點，即所謂的增量，
等距的一些元素先排序，再逐漸過渡到整個數組。
(增量的選擇很關鍵，有很多研究)
時間複雜度：最差最好：O(nlogn)
空間複雜度：O(1)
'''
def ShellSort(li):
    def shellinsert(li, d):
        n = len(li)
        for i in range(d, n):
            j = i - d
            temp = li[i]
            while (j >= 0 and li[j] > temp):
                li[j+d] = li[j]
                j -= d
            if j != i-d:
                li[j+d] = temp
    n = len(li)
    if n <= 1:
        return li
    d = n // 2
    while d >= 1:
        shellinsert(li, d)
        d //= 2
    return li

'''堆排序
選擇理由：簡單選擇排序沒有很好利用第一次比較的結果，是以改進為堆排序。不穩定。
基本思想:建堆：從最後一個非葉子節點開始調整到根節點；
排序：從根節點取出數放在最後面n-1次。
時間複雜度：最差最好都是：O(nlogn)這就很厲害了！
空間複雜度：O(1)
'''
def HeapSort(li):
    def heapadjust(li, root, end):
        temp = li[root]
        son = 2*root+1
        while son <= end:
            if son < end and li[son] < li[son+1]:
                son += 1
            if temp > li[son]:
                break
            li[root] = li[son]
            root = son
            son = root*2+1

    n = len(li)
    if n <= 1:
        return
    root = n//2-1
    while root >= 0:#建立堆
        heapadjust(li, root, n-1)
        root -= 1
    i = n-1
    while i > 0:#排序
        li[i],li[0] = li[0],li[i]
        heapadjust(li, 0, i-1)
        i -= 1
    return li

'''歸并排序-分治遞歸的思想,代碼為二路歸并
選擇理由：穩定，一般用于總體無序，但各子項相對有序。
基本思想:将清單分成幾部分，兩兩合并。
時間複雜度：平均最差最好都是：O(nlogn)這就很厲害了！
空間複雜度：O(n)
'''
def MergeSort(li):
    #合并左右子序列函數
    def merge(li, left, mid, right):
        temp = [] #中間數組
        i = left#左段子序列起始
        j = mid + 1#右段子序列起始
        while i<= mid and j <= right:
            if li[i] < li[j]:
                temp.append(li[i])
                i += 1
            else:
                temp.append(li[j])
                j += 1
        while i <= mid:
            temp.append(li[i])
            i += 1
        while j <= right:
            temp.append(li[j])
            j += 1
        # !注意這裡，不能直接li=temp,他倆大小都不一定一樣
        for i in range(left, right+1):
            li[i] = temp[i-left]
    #遞歸調用歸并排序
    def msort(li, left, right):
        if left >= right:
            return
        mid = (left+right)//2
        mSort(li, left, mid)
        mSort(li, mid+1, right)
        merge(li, left, mid, right)

    n = len(li)
    if n <= 1:
        return li
    mSort(li, 0, n-1)
    return li

'''桶排序：工作的原理是将數組分到有限數量的桶子裡。每個桶子再個别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排序）。當要被排序的數組内的數值是均勻配置設定的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是比較排序，他不受到 O(n log n)下限的影響。
經典應用：
應用：給500萬考生成績排序，超級快。适用于元素集合不大的情況，分數集合最多是0-1000。
應用：在一個檔案中有10G個整數，亂序排列，要求找出中位數。記憶體限制為2G。隻寫出思路即可
'''
def bucketSort(nums):
  # 選擇一個最大的數
  max_num = max(nums)
  # 建立一個元素全是0的清單, 當做桶
  bucket = [0]*(max_num+1)
  # 把所有元素放入桶中, 即把對應元素個數加一
  for i in nums:
    bucket[i] += 1
  # 存儲排序好的元素
  sort_nums = []
  # 取出桶中的元素
  for j in range(len(bucket)):
    if bucket[j] != 0:
      for y in range(bucket[j]):
        sort_nums.append(j)
  return sort_nums
nums = [5,6,3,2,1,65,2,0,8,0]
print "腳本之家測試結果:"
print bucketSort(nums)

'''快速排序-20世紀十大算法之一
選擇理由：不穩定，但是後序研究豐富，很多優化方案。進行優化後，該排序算法依舊很強！冒泡排序的改進！
改進雖然好，但是對于大資料是好事，但是如果資料本身就很小，就有點大炮打蚊子，
反而更費事了。
優化4：資料較小更換排序算法
基本思想:選一個數作為中間樞紐，進行清單的劃分，遞歸。
時間複雜度：最差：O(n2)最好：O(nlogn)
空間複雜度：主要為遞歸造成的空間棧的使用，O(n)
'''
def QuickSort(li):
    def partition(li, left, right):
        key = left#優化1：三數取中或者九數，而不随便取一個
        while left < right:
            while left < right and li[right] > li[key]:
                right -= 1
            while left < right and li[left] < li[key]:
                left += 1
            li[left],li[right] = li[right],li[left]
        #優化2：直接進行交換，最後再插入中間樞紐:。
        li[key],li[left] = li[left],li[key]
        return left

    def quicksort(li, left, right):#遞歸調用
        if left >= right:
            return
        mid = partition(li, left, right)
        quicksort(li, left, mid-1)
#優化3：減少遞歸棧空間的使用，使用疊代
#while循環加上left = mid + 1
        quicksort(li, mid+1, right)
    #主函數
    n = len(li)
    if n <= 1:
        return li
    quicksort(li, 0, n-1)
    return li