排序演算法 ||蟒蛇 ||資料結構和演算法-Python教學-PHP中文網

首頁

後端開發

Python教學

排序演算法 ||蟒蛇 ||資料結構和演算法

Mary-Kate Olsen

Dec 18, 2024 am 09:08 AM

Sorting Algorithms || Python || Data Structures and Algorithms

排序演算法

1. 冒泡排序

在此，我們將較高的元素與其相鄰的元素交換，直到到達陣列的末端。現在最高的元素位於最後一個位置。因此，我們更改邊界並將其比上一個減少 1。在最壞的情況下，我們必須迭代 n 次才能對陣列進行排序。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

登入後複製

演算法 -

迭代數組並找到最大元素，然後將其交換到最後一個。
比較所有相鄰元素，如果較大的元素在較小的元素之前，則交換。繼續這樣做，直到到達數組的末尾。
維護一個標誌：如果沒有元素被交換，那麼我們可以打破循環，因為陣列已排序。

時間複雜度：

最佳情況 - 如果陣列已經排序，則只需要一次迭代。時間複雜度 - O(n)
平均情況 - 如果陣列是隨機排序的，則時間複雜度 - O(n2)
最壞情況 - 如果陣列按降序排列，那麼我們將需要 n*2 次迭代。

空間複雜度 - O(1)，不需要額外的記憶體。

優點 -

無需額外記憶體。
穩定，因為元素保持其相對順序。

缺點 -

時間複雜度 - O(n2)，對於大型資料集來說非常高。

應用-

僅當資料集非常小時才可使用，且由於時間複雜度較高，簡單性勝過低效率。

2. 選擇排序

在此，我們找到數組中最小的元素並將其替換為第一個元素。然後，我們將邊界增加 1 並重複相同的步驟，直到我們到達陣列的末端。

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

登入後複製

演算法 -

迭代數組並找到最小元素。
與第一個元素交換位置，指針加1。
重複此過程，直到到達數組末尾。

時間複雜度：在所有三種情況下其時間複雜度均為 O(n2)：最佳、平均和最差。 這是因為我們必須選擇最小元素並且每次都交換它，無論數組是否已經排序。

空間複雜度 - O(1)，不需要額外的記憶體。

優點 -

無需額外記憶體。
比冒泡排序進行的交換更少。

缺點 -

時間複雜度 - O(n2)，對於大型資料集來說非常高。
不穩定，因為它不保持相等元素的相對順序。

應用程式 -

它可以在記憶體有限的系統中使用，因為它不需要額外的儲存空間。
它用於最小化交換次數至關重要的系統，例如寫入操作緩慢的系統。

3.插入排序

這是一種演算法，透過從元素位置到陣列開頭迭代地向後檢查，將未排序的元素插入到正確的位置。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

登入後複製

演算法 -

從陣列的第二個元素開始，與第一個元素進行比較。如果目前元素小於第一個元素，則交換它們。
現在增加指標並對第三個元素執行此操作：將其與第二個和第一個元素進行比較。
對其餘元素重複相同的過程，將它們與先前的所有元素進行比較，並將它們插入到適當的位置。

時間複雜度：

- 最佳情況 - 如果陣列已經排序，則只需要一次迭代。時間複雜度為 O(n)
- 平均情況 - 如果陣列是隨機排序的，那麼時間複雜度是 O(n2)
- 最壞情況 - 如果陣列按降序排列，那麼我們將需要 n2 次迭代。

空間複雜度 - O(1)，不需要額外的記憶體。

優點 -

不需要額外的記憶體。
穩定，因為元素保持其相對順序。

缺點 -

時間複雜度 - O(n2)，對於大型資料集來說非常高。
不穩定，因為它不保持相等元素的相對順序。

應用-

對於即時資料流等元素即時到達且需要排序的場景非常有效率。

4. 歸併排序

歸併排序是一種遵循分而治之方法的演算法。它有兩個主要步驟：首先，遞歸地劃分數組，其次，按排序順序合併劃分後的數組。

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

登入後複製

演算法 -

透過計算中點將陣列分成兩半。
繼續劃分，直到每個子數組的長度為1。
在兩半上呼叫合併函數：左半部和右半部。
使用三個指標合併過程：

左半數組的第一個指標。
右半數組的第二個指標。
已排序數組的第三個指標。

迭代兩半並比較它們的元素。將較小的元素插入已排序的陣列中，並將對應的指標加 1。
遞歸地重複此過程，直到整個陣列排序完畢。

時間複雜度：歸併排序在所有三種情況下的時間複雜度均為O(n log n)：最佳、平均和最差。這是因為，無論數組是否已經排序，每次劃分和合併都會遵循相同的步驟。

O( log n ) - 在除法階段的每一步，陣列大小減半。

O(n) - 在合併過程中，我們必須迭代所有元素一次。

所以總時間複雜度為 O (n) * O(log n) = O (n log n)

空間複雜度 - O(n)，合併過程中需要額外的記憶體來儲存臨時數組。

優點 -

穩定，因為元素保持其相對順序。
即使對於大型資料集，時間複雜度也是 O (n log n)。
適合併行處理，因為子數組是獨立合併的。

缺點 -

時間複雜度 - O(n2)，對於大型資料集來說非常高。
合併過程需要額外的記憶體。
未到位，因為需要額外的記憶體。
對於大多數資料集來說通常比快速排序慢。

應用程式 -

用於資料太大而無法放入記憶體的情況，例如合併大檔案。
它用於對鍊錶進行排序，因為不需要隨機存取。

5. 快速排序

快速排序是一種遵循分而治之方法的演算法。我們選擇一個主元元素，並將主元放在正確的排序位置後，圍繞主元元素對陣列進行分區。

第一步是選擇主元元素，然後圍繞主元對陣列進行分割。所有小於主元的元素都將位於左側，所有大於主元的元素將位於其右側。然後樞軸位於正確的排序位置。遞歸地，透過將陣列分成兩半來應用相同的過程：前半部包含主元之前的元素，後半部包含主元之後的元素。重複這個過程，直到每個子數組的長度達到1。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

登入後複製

演算法 -

透過計算中點將陣列分成兩半。
選擇一個樞軸；可以選擇任何元素作為基準。
迭代數組並將每個元素與主元進行比較。
將所有小於主元的元素放置在左側，將所有大於主元的元素放置在右側。
將樞軸與左指針交換，使樞軸位於正確的排序位置。
遞歸地重複這個過程，直到分區的長度大於1。

時間複雜度：

1。最佳情況 - 時間複雜度 - O(n log n)，當主元將陣列分成相等的兩半。
2.平均情況 - 時間複雜度 - O(n log n)，當主元將陣列分成相等的兩半。但不一定相等。
3.最壞情況 - 時間複雜度 - O(n2) ，當 -

在已經排序的陣列中選擇最小的元素作為主元。
選擇最大元素作為按降序排序的陣列中的主元。

O( log n ) - 在除法階段的每一步，陣列大小減半。

O(n) - 在元素排序期間。

所以，總時間複雜度為 O(n) * O(log n) = O (n log n)

空間複雜度：

最佳和平均情況 - O(log n) - 用於遞歸堆疊。
最壞情況 - O(n) - 對於遞歸堆疊。

優點 -

對於大型資料集非常有效，除非樞軸選擇不當。
它是快取友善的，因為我們在同一個陣列上進行排序，並且不將資料複製到任何輔助數組。
在不需要穩定性時，用於大數據的最快通用演算法之一。

缺點 -

時間複雜度 - O(n2)，對於大型資料集來說非常高。
不穩定，因為它不能維持相等元素的相對順序。

應用程式 -

它用於程式設計庫和框架。例如-Python的sorted()函數和Java的Array.sort()是基於快速排序。
它透過在查詢執行期間有效地對行進行排序來使用 indDatabase 查詢最佳化。
由於其快取友好的特性，它非常適合大型資料集的記憶體排序。

6.堆排序

堆排序是一種基於比較的排序演算法。它是選擇排序的擴展。在堆排序中，我們建立一個二元堆並將最大或最小元素與最後一個元素交換。然後，我們將堆大小減少 1。重複此過程，直到堆的長度大於 1。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

登入後複製

演算法 -

使用 heapify 進程建立最大堆。 Heapify 是一種用於維護二元堆資料結構的堆屬性的方法。
如果陣列大小為 n，則包含 n//2 個父節點。
對於索引 i 處的父級：

a.它的左子節點位於索引 2i 1

b.它的右子節點位於索引 2i 2

迭代所有父級從索引 n//2 到 0 的子樹，並對它們呼叫 heapify 函數。
現在，數組成為最大堆，最大元素位於索引 0。
將堆的第一個元素與最後一個元素交換，並將堆的大小減少 1。
重複這個過程，直到堆的長度大於1

時間複雜度：堆排序在所有三種情況下的時間複雜度均為 O(n log n)：最佳、平均和最差。這是因為，無論數組是否已經排序，每次創建最大堆和交換元素時都會遵循相同的步驟。

O( log n ) - 建立最大堆

O(n) - 建立最大堆並且交換元素 n 次。

所以總時間複雜度為 O(n) * O(log n) = O(n log n)

空間複雜度：對於所有情況 - O(log n) - 對於遞歸堆疊。

優點 -

即使對於大型資料集，時間複雜度也是 O (n log n)。
記憶體使用率幾乎恆定。

缺點 -

不穩定，因為它不能維持相等元素的相對順序。
與合併排序相比，需要很多交換。

應用程式 -

對於實現頻繁提取最大或最小元素的優先權隊列非常有用。
在需要就地排序且記憶體使用至關重要的系統中很有用。
用於需要排名的場景。

7.計數排序和基數排序

計數排序是一種非基於比較的排序演算法。當輸入值的範圍與要排序的元素的數量相比較小時，它特別有效。計數排序背後的基本思想是計算輸入數組中每個不同元素的頻率，並使用該資訊將元素放置在正確的排序位置。

基數排序使用計數排序作為子程式。它將計數排序應用於數字的每個數字位元並重複排序，直到處理完數組中最大數字的所有數字。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

登入後複製

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

登入後複製

演算法 -