幾種排序算法及 Python 實現(xiàn)

cod7ce 發(fā)布于2019-07-31 11:05 / 3043人閱讀

摘要：因為直接插入排序在元素基本有序的情況下接近最好情況，效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

插入排序

def insert_sort(list):
    n = len(list)
    for i in range(1, n):
        key = list[i]
        for j in range(i-1, -1, -1):
            if list[j] > key:
                list[j+1], list[j] = list[j], key
            else:
                break
    return list
   
print(insert_sort([3, 2, 5, 1, 4]))

希爾(縮小增量)排序

算法課沒有講希爾排序，所以記錄一下其思想和復雜度分析

該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

時間復雜度與步長選擇有關，最壞情況下 $$ O(n^2) $$
不穩(wěn)定

以 gap 替換插入排序中的 1

def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n, gap):
            key = list[i]
            for j in range(i-gap, -1, -gap):
                if key < list[j]:
                    list[j+gap], list[j] = list[j], key
                else:
                    break
        gap //= 2
    return list

快排

def quick_sort(list, left, right):
    if left >= right:
        return list
    key = list[right]
    high = right - 1
    low = left
    while low <= high:
        if list[low] > key:
            list[low], list[high] = list[high], list[low]
            high -= 1
        else:
            low += 1
    list[low], list[right] = list[right], list[low]
    quick_sort(list, left, low-1)
    quick_sort(list, low+1, right)
    return list
print(quick_sort([3, 2, 5, 1, 4, 6, 8, 7], 0, 7))

堆排序

def adjust_heap(list, i, n):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if lchild < n and list[lchild] > list[max]:
        max = lchild
    if rchild < n and list[rchild] > list[max]:
        max = rchild
    if max != i:
        list[i], list[max] = list[max], list[i]
        adjust_heap(list, max, n)
        
def build_heap(list, n):
    for i in range(int(n/2)-1, -1, -1):
        adjust_heap(list, i, n)

def heap_sort(list):
    build_heap(list, len(list))
    for i in range(len(list)-1, -1, -1):
        list[0], list[i] = list[i], list[0]
        adjust_heap(list, 0, i)
    return list
list = [3, 2, 5, 1, 4, 6, 8, 7]
print(heap_sort(list))

歸并排序

自頂向下的遞歸實現(xiàn)：
$$T(n)=2Tleft(frac{n}{2} ight)+O(n)$$
$$Rightarrow T(n)=O(nlog n)$$

def merge(list1, list2):
    res = []
    n, m = len(list1), len(list2)
    i, j = 0, 0
    while i < n and j < m:
        if list1[i] < list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    res += list1[i:]
    res += list2[j:]
    return res

def merge_sort(list):
    n = len(list)
    if n <= 1:
        return list
    left = merge_sort(list[:n//2])
    right = merge_sort(list[n//2:])
    return merge(left, right)

云服務器 GPU云服務器排序算法圖解排序算法總結桶排序算法學習排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44629.html

Javag工程師成神之路（2019正式版）

摘要：結構型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責鏈模式責任鏈模式訪問者模式。主要版本更新時間備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術知識、完善知識體系 v2.0 2019-02-19 結構...

Olivia 2019-08-16 15:14 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

pumpkin9 2019-08-23 17:12 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

Carson 2019-07-31 10:21 評論0 收藏0
前端面試題總結（js、html、小程序、React、ES6、Vue、算法、全棧熱門視頻資源）

摘要：并總結經典面試題集各種算法和插件前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快速搭建項目。本文是關注微信小程序的開發(fā)和面試問題，由基礎到困難循序漸進，適合面試和開發(fā)小程序。并總結vue React html css js 經典面試題集各種算法和插件、前端視頻源碼資源于一身的文檔，優(yōu)化項目，在瀏覽器端的層面上提升速度，幫助初中級前端工程師快...

muzhuyu 2019-07-01 12:43 評論0 收藏0