分享Python常用的排序實例

• 排序演算法的穩定性及意義

• 冒泡排序

• ##複雜度與穩定性

• 選擇排序

• #插入排序

##」希爾排序

• ##快速排序

常見排序演算法效率比較

排序演算法的穩定性與意義

在待排序的序列中，存在具有相同關鍵字的記錄，在排序後這些記錄的相對次序保持不變，則排序演算法是穩定的。 不穩定排序無法完成多個關鍵字的排序。例如整數排序，位數越高的數字優先權越高，從高位數到低位數一次排序。那麼每一位的排序都需要穩定演算法，否則無法得到正確的結果。

即，

當要對多個關鍵字進行多次排序時，必須使用穩定演算法

#冒泡排序



• def bubble_sort(alist):
      """
      冒泡排序
      """
      if len(alist)  alist[i+1]:
                  alist[i], alist[i+1] = alist[i+1], alist[i]
  
      return alist

  複雜度與穩定性

• 最優時間複雜度：\(O(n)\) 遍歷沒有發現任何可以交換的元素，排序結束

• 最糟時間複雜度：\(O(n^2)\)

#穩定性：穩定

選擇排序

• 選擇排序（Selection sort）是一種簡單直覺的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末端。以此類推，直到所有元素都排序完畢。

插入排序

• 插入排序透過建立有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實作上，從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。



def insert_sort(alist):
    """
    插入排序
    """
    n = len(alist)
    if n  0:
            alist[j], alist[j-1] = alist[j-1], alist[j]
            j-=1
    return alist

複雜度與穩定性

#最優時間複雜度：O(\(n\)) (升序排列，序列已經處於升序狀態）

• 最壞時間複雜度：O(\(n^2\))

• 穩定性：穩定

• 希爾排序
  希爾排序(Shell Sort)是插入排序的改進, 排序非穩定。希爾排序是把記錄按標的一定
增量

分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減至1時，整份文件恰被分成一組，演算法便終止。

def shell_sort(alist):
    
    n = len(alist)
    gap = n//2
    
    # gap 变化到0之前，插入算法之行的次数
    while gap > 0:
        
        # 希尔排序， 与普通的插入算法的区别就是gap步长
        for i in range(gap,n):
            j = i
            while alist[j]  0:
                alist[j], alist[j-gap] = alist[j-gap], alist[j]
                j-=gap
    
        gap = gap//2

    return alist

複雜度與穩定性

最優時間複雜度：\(O(n^{1.3})\) （不要求本身有順序）

1. 最壞時間複雜度：\(O(n^2)\)

2. 穩定性：不穩定

3. 快速排序

快速排序(Quicksort)，透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法將這兩部分資料分別進行快速排序，整個排序過程可以遞歸進行，以達到整個資料變成有序序列。

步驟為：

#########重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分區(partition)操作。 ############遞歸地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序。 ############遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總是會結束，因為在每次的迭代(iteration)中，它至少會把一個元素擺到它最後的位置去。 ######常見排序演算法效率比較############

以上是分享Python常用的排序實例的詳細內容。更多資訊請關注PHP中文網其他相關文章！