分享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^2\))

• 穩定性：穩定

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

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

登入後複製

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

2. 穩定性：不穩定

3. 快速排序

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

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