歡迎光臨
每天分享高質量文章

GitHub星數13200!用Python實現所有排序演算法的開源專案你見過麽?

開源最前線(ID:OpenSourceTop) 整編

綜合自:GitHub詳情頁

GitHub月度Trending榜單已經出爐,感興趣的伙伴可點擊查看上榜前十的開源專案:《9月份GitHub上最熱門的開源專案》

本月榜單有一個專案成功吸引了我的註意,該專案用Python實現了所有的排序演算法,包括插入排序、冒泡排序、快速排序、選擇排序、歸併排序等。

截至今日,該專案已經獲得了 13200 個「star」以及 3758 個「fork」(GitHub專案地址:https://github.com/TheAlgorithms/Python

該創建者表示這些僅用於演示學習。由於性能的原因,Python標準庫中有許多排序實現。

1、冒泡排序

冒泡排序,有時也稱為下沉排序,是一種簡單的排序演算法,它反覆遍歷要排序的串列,一次比較兩個元素,如果它們的順序錯誤則交換它們。重覆遍歷串列,直到不再需要交換,說明該串列排序完成。

性能分析

● 冒泡排序在最壞的情況下的比較次數是O(N^2) 

● 冒泡排序在最壞的情況下的比較次數是O(N)

代碼實現

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] 1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

2、插入排序 

插入排序是一種簡單的排序演算法,可以一次構建一個專案的最終排序陣列(或串列)。它在大型串列上的效率遠低於更高級的演算法,如快速排序,對堆排序或歸併排序。

代碼實現

for i = 2:n,
    for (k = i; k > 1 and a[k] 1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

3、歸併排序

歸併排序(MERGE-SORT)是一種有效的、通用的,基於比較的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。由John von Neumann於1945年發明。

屬性

● 最好時間複雜度O(nlogn)

● 最壞時間複雜度O(nlogn)

● 平均時間複雜度O(nlogn)

代碼實現

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j]     → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

歸併排序在多種情況下都是首選的演算法:當需要穩定性時,當排序鏈表時,當隨機訪問比順序訪問複雜得多時(例如,磁帶上的外部排序)。

4、快速排序

快速排序(也被稱為分割槽交換排序)是一種有效的排序演算法,用作按順序放置陣列元素的系統方法。

代碼實現

_# choose pivot_
swap a[1,rand(1,n)]

_# 2-way partition_
k = 1
for i = 2:n, if a[i] 1], swap a[++k,i]
swap a[1,k]
_→ invariant: a[1..k-1] 1..n]_

_# recursive sorts_
sort a[1..k-1]
sort a[k+1,n]

5、選擇排序

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的資料元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的資料元素排完。 

代碼實現

for i = 1:n,
    k = i
    for j = i+1:nif a[j]     → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

選擇排序的特性是最小化交換的數量。在交換項成本很高的應用程式中,選擇排序可能是一種很好的選擇演算法。

6、希爾排序

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序演算法的改進。該方法又稱縮小增量排序,因D.L.Shell於1959年提出而得名。

屬性

● 最好時間複雜度O(nlog2 2n)

● 最壞時間複雜度O(n log n)

● 平均時間複雜度表現取決於差距序列

實現代碼

h = 1
while h 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end


●編號529,輸入編號直達本文

●輸入m獲取文章目錄

赞(0)

分享創造快樂