排序演算法

1. 冒泡排序

在此，我們將較高的元素與其相鄰的元素交換，直到到達(dá)陣列的末端?，F(xiàn)在最高的元素位於最後一個(gè)位置。因此，我們更改邊界並將其比上一個(gè)減少 1。在最壞的情況下，我們必須迭代 n 次才能對陣列進(jì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

演算法 -

1. 迭代數(shù)組並找到最大元素，然後將其交換到最後一個(gè)。
2. 比較所有相鄰元素，如果較大的元素在較小的元素之前，則交換。繼續(xù)這樣做，直到到達(dá)數(shù)組的末尾。
3. 維護(hù)一個(gè)標(biāo)誌：如果沒有元素被交換，那麼我們可以打破循環(huán)，因?yàn)殛嚵幸雅判颉?

時(shí)間複雜度：

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

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

優(yōu)點(diǎn) -

1. 無需額外記憶體。

2. 穩(wěn)定，因?yàn)樵乇３制湎鄬樞颉?

缺點(diǎn) -

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

應(yīng)用-

1. 僅當(dāng)資料集非常小時(shí)才可使用，且由於時(shí)間複雜度較高，簡單性勝過低效率。

2. 選擇排序

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

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. 迭代數(shù)組並找到最小元素。

2. 與第一個(gè)元素交換位置，指針加1。

3. 重複此過程，直到到達(dá)數(shù)組末尾。

時(shí)間複雜度：在所有三種情況下其時(shí)間複雜度均為 O(n2)：最佳、平均和最差。 這是因?yàn)槲覀儽仨氝x擇最小元素並且每次都交換它，無論數(shù)組是否已經(jīng)排序。

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

優(yōu)點(diǎn) -

1. 無需額外記憶體。

2. 比冒泡排序進(jìn)行的交換更少。

缺點(diǎn) -

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

2. 不穩(wěn)定，因?yàn)樗槐３窒嗟仍氐南鄬樞颉?

應(yīng)用程式 -

1. 它可以在記憶體有限的系統(tǒng)中使用，因?yàn)樗恍枰~外的儲(chǔ)存空間。

2. 它用於最小化交換次數(shù)至關(guān)重要的系統(tǒng)，例如寫入操作緩慢的系統(tǒng)。

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

演算法 -

1. 從陣列的第二個(gè)元素開始，與第一個(gè)元素進(jìn)行比較。如果目前元素小於第一個(gè)元素，則交換它們。

2. 現(xiàn)在增加指標(biāo)並對第三個(gè)元素執(zhí)行此操作：將其與第二個(gè)和第一個(gè)元素進(jìn)行比較。

3. 對其餘元素重複相同的過程，將它們與先前的所有元素進(jìn)行比較，並將它們插入到適當(dāng)?shù)奈恢谩?

時(shí)間複雜度：

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

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

優(yōu)點(diǎn) -

1. 不需要額外的記憶體。
2. 穩(wěn)定，因?yàn)樵乇３制湎鄬樞颉?

缺點(diǎn) -

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

2. 不穩(wěn)定，因?yàn)樗槐３窒嗟仍氐南鄬樞颉?

應(yīng)用-

1. 對於即時(shí)資料流等元素即時(shí)到達(dá)且需要排序的場景非常有效率。

4. 歸併排序

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

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. 透過計(jì)算中點(diǎn)將陣列分成兩半。

2. 繼續(xù)劃分，直到每個(gè)子數(shù)組的長度為1。

3. 在兩半上呼叫合併函數(shù)：左半部和右半部。

4. 使用三個(gè)指標(biāo)合併過程：

• 左半數(shù)組的第一個(gè)指標(biāo)。
• 右半數(shù)組的第二個(gè)指標(biāo)。
• 已排序數(shù)組的第三個(gè)指標(biāo)。

1. 迭代兩半並比較它們的元素。將較小的元素插入已排序的陣列中，並將對應(yīng)的指標(biāo)加 1。

2. 遞歸地重複此過程，直到整個(gè)陣列排序完畢。

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

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

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

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

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

優(yōu)點(diǎn) -

1. 穩(wěn)定，因?yàn)樵乇３制湎鄬樞颉?

2. 即使對於大型資料集，時(shí)間複雜度也是 O (n log n)。

3. 適合併行處理，因?yàn)樽訑?shù)組是獨(dú)立合併的。

缺點(diǎn) -

1. 時(shí)間複雜度 - O(n2)，對於大型資料集來說非常高。
2. 合併過程需要額外的記憶體。
3. 未到位，因?yàn)樾枰~外的記憶體。
4. 對於大多數(shù)資料集來說通常比快速排序慢。

應(yīng)用程式 -

1. 用於資料太大而無法放入記憶體的情況，例如合併大檔案。
2. 它用於對鍊錶進(jìn)行排序，因?yàn)椴恍枰S機(jī)存取。

5. 快速排序

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

第一步是選擇主元元素，然後圍繞主元對陣列進(jìn)行分割。所有小於主元的元素都將位於左側(cè)，所有大於主元的元素將位於其右側(cè)。然後樞軸位於正確的排序位置。遞歸地，透過將陣列分成兩半來應(yīng)用相同的過程：前半部包含主元之前的元素，後半部包含主元之後的元素。重複這個(gè)過程，直到每個(gè)子數(shù)組的長度達(dá)到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. 透過計(jì)算中點(diǎn)將陣列分成兩半。
2. 選擇一個(gè)樞軸；可以選擇任何元素作為基準(zhǔn)。
3. 迭代數(shù)組並將每個(gè)元素與主元進(jìn)行比較。
4. 將所有小於主元的元素放置在左側(cè)，將所有大於主元的元素放置在右側(cè)。
5. 將樞軸與左指針交換，使樞軸位於正確的排序位置。
6. 遞歸地重複這個(gè)過程，直到分區(qū)的長度大於1。

時(shí)間複雜度：

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

• 在已經(jīng)排序的陣列中選擇最小的元素作為主元。

• 選擇最大元素作為按降序排序的陣列中的主元。

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

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

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

空間複雜度：

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

2. 最壞情況 - O(n) - 對於遞歸堆疊。

優(yōu)點(diǎn) -

1. 對於大型資料集非常有效，除非樞軸選擇不當(dāng)。
2. 它是快取友善的，因?yàn)槲覀冊谕粋€(gè)陣列上進(jìn)行排序，並且不將資料複製到任何輔助數(shù)組。
3. 在不需要穩(wěn)定性時(shí)，用於大數(shù)據(jù)的最快通用演算法之一。

缺點(diǎn) -

1. 時(shí)間複雜度 - O(n2)，對於大型資料集來說非常高。
2. 不穩(wěn)定，因?yàn)樗荒芫S持相等元素的相對順序。

應(yīng)用程式 -

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

6.堆排序

堆排序是一種基於比較的排序演算法。它是選擇排序的擴(kuò)展。在堆排序中，我們建立一個(gè)二元堆並將最大或最小元素與最後一個(gè)元素交換。然後，我們將堆大小減少 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

演算法 -

1. 使用 heapify 進(jìn)程建立最大堆。 Heapify 是一種用於維護(hù)二元堆資料結(jié)構(gòu)的堆屬性的方法。
2. 如果陣列大小為 n，則包含 n//2 個(gè)父節(jié)點(diǎn)。
3. 對於索引 i 處的父級(jí)：

a.它的左子節(jié)點(diǎn)位於索引 2i 1

b.它的右子節(jié)點(diǎn)位於索引 2i 2

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

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

O( log n ) - 建立最大堆

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

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

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

優(yōu)點(diǎn) -

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

缺點(diǎn) -

1. 不穩(wěn)定，因?yàn)樗荒芫S持相等元素的相對順序。
2. 與合併排序相比，需要很多交換。

應(yīng)用程式 -

1. 對於實(shí)現(xiàn)頻繁提取最大或最小元素的優(yōu)先權(quán)隊(duì)列非常有用。
2. 在需要就地排序且記憶體使用至關(guān)重要的系統(tǒng)中很有用。
3. 用於需要排名的場景。

7.計(jì)數(shù)排序和基數(shù)排序

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

基數(shù)排序使用計(jì)數(shù)排序作為子程式。它將計(jì)數(shù)排序應(yīng)用於數(shù)字的每個(gè)數(shù)字位元並重複排序，直到處理完數(shù)組中最大數(shù)字的所有數(shù)字。

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

演算法 -

1. 找出數(shù)組中的最大數(shù)字並確定其中的位數(shù) (d)。如果數(shù)字的長度為 d，則在陣列上呼叫計(jì)數(shù)排序 d 次。

2. 對數(shù)組中的每個(gè)數(shù)字位置呼叫計(jì)數(shù)排序，從個(gè)位開始，然後是十位，依此類推。

3. 計(jì)數(shù)排序：

• 首先，建立一個(gè)索引數(shù)組，並根據(jù)元素的值來對應(yīng)元素。例如，如果數(shù)字為 4，則在索引數(shù)組的第 4 個(gè)索引處遞增值。
• 從索引陣列建立前綴和陣列。
• 使用前綴和數(shù)組，建立一個(gè)等於輸入數(shù)組長度的新排序數(shù)組
• 例如，如果前綴和數(shù)組在索引 1 處的值為 2，則將值 1 放置在排序數(shù)組中的位置 2 處，並將前綴和數(shù)組中的值遞減 1

時(shí)間複雜度：

計(jì)數(shù)排序 的時(shí)間複雜度為 O(n k)，其中 n 是要排序的元素?cái)?shù)量，k 是值的範(fàn)圍（索引數(shù)組的大?。?。此複雜度適用於所有三種情況：最佳、平均和最差。

這是因?yàn)?，無論陣列是否已經(jīng)排序，每次都會(huì)遵循相同的步驟。

基數(shù)排序時(shí)間複雜度增加了 d 倍，其中 d 是陣列中最大數(shù)字的位數(shù)。時(shí)間複雜度為 O(d * (n k))

所以總時(shí)間複雜度為 O (d) * O(n k) = O (d * (n k))

空間複雜度：對於所有情況 - O(n k)，其中 n 是輸入數(shù)組的長度，k 是索引數(shù)組中的值的範(fàn)圍。

優(yōu)點(diǎn) -

1. 由於元素保持其相對順序而穩(wěn)定。
2. 如果輸入範(fàn)圍與輸入數(shù)量相同，則計(jì)數(shù)排序通常比所有基於比較的排序演算法（例如合併排序和快速排序）執(zhí)行得更快。

缺點(diǎn) -

1. 計(jì)數(shù)排序不適用於小數(shù)值。
2. 如果要排序的值範(fàn)圍很大，計(jì)數(shù)排序效率很低。
3. 非就地排序演算法，因?yàn)樗褂妙~外的空間 O(O(n m))。

應(yīng)用程式 -

1. 它用於計(jì)算字串中字元出現(xiàn)次數(shù)等應(yīng)用程式。
2. 對於對具有大範(fàn)圍值的整數(shù)進(jìn)行排序非常有用，例如 ID 或電話號(hào)碼。
3. 可以有效地對具有多個(gè)鍵的資料進(jìn)行排序，例如日期或元組。

以上是排序演算法 ||蟒蛇 ||資料結(jié)構(gòu)和演算法的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！