排序算法

1. 冒泡排序

在此，我們將較高的元素與其相鄰的元素交換，直到到達(dá)數(shù)組的末尾?，F(xiàn)在最高的元素位于最后一個(gè)位置。因此，我們更改邊界并將其比上一個(gè)減少 1。最壞的情況下，我們必須迭代 n 次才能對(duì)數(shù)組進(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)志：如果沒(méi)有元素被交換，那么我們可以打破循環(huán)，因?yàn)閿?shù)組已排序。

時(shí)間復(fù)雜度：

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

空間復(fù)雜度 - O(1)，不需要額外的內(nèi)存。

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

1. 無(wú)需額外內(nèi)存。

2. 穩(wěn)定，因?yàn)樵乇３制湎鄬?duì)順序。

缺點(diǎn) -

1. 時(shí)間復(fù)雜度 - O(n2)，對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)非常高。

應(yīng)用-

1. 僅當(dāng)數(shù)據(jù)集非常小時(shí)才可以使用，并且由于時(shí)間復(fù)雜度較高，簡(jiǎn)單性勝過(guò)低效率。

2. 選擇排序

在此，我們找到數(shù)組中最小的元素并將其替換為第一個(gè)元素。然后，我們將邊界增加 1 并重復(fù)相同的步驟，直到到達(dá)數(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. 迭代數(shù)組并找到最小元素。

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

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

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

空間復(fù)雜度 - O(1)，不需要額外的內(nèi)存。

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

1. 無(wú)需額外內(nèi)存。

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

缺點(diǎn) -

1. 時(shí)間復(fù)雜度 - O(n2)，對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)非常高。

2. 不穩(wěn)定，因?yàn)樗槐３窒嗟仍氐南鄬?duì)順序。

應(yīng)用程序 -

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

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

3.插入排序

這是一種算法，通過(guò)從元素位置到數(shù)組開(kāi)頭迭代地向后檢查，將未排序的元素插入到正確的位置。

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è)元素開(kāi)始，與第一個(gè)元素進(jìn)行比較。如果當(dāng)前元素小于第一個(gè)元素，則交換它們。

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

3. 對(duì)其余元素重復(fù)相同的過(guò)程，將它們與之前的所有元素進(jìn)行比較，并將它們插入到合適的位置。

時(shí)間復(fù)雜度：

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

空間復(fù)雜度 - O(1)，不需要額外的內(nèi)存。

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

1. 不需要額外的內(nèi)存。
2. 穩(wěn)定，因?yàn)樵乇３制湎鄬?duì)順序。

缺點(diǎn) -

1. 時(shí)間復(fù)雜度 - O(n2)，對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)非常高。

2. 不穩(wěn)定，因?yàn)樗槐３窒嗟仍氐南鄬?duì)順序。

應(yīng)用-

1. 對(duì)于實(shí)時(shí)數(shù)據(jù)流等元素實(shí)時(shí)到達(dá)且需要排序的場(chǎng)景非常高效。

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. 通過(guò)計(jì)算中點(diǎn)將數(shù)組分成兩半。

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

3. 在兩半上調(diào)用合并函數(shù)：左半部分和右半部分。

4. 使用三個(gè)指針進(jìn)行合并過(guò)程：

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

1. 迭代兩半并比較它們的元素。將較小的元素插入已排序的數(shù)組中，并將相應(yīng)的指針加 1。

2. 遞歸地重復(fù)此過(guò)程，直到整個(gè)數(shù)組排序完畢。

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

O( log n ) - 在除法階段的每一步，數(shù)組大小減半。

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

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

空間復(fù)雜度 - O(n)，合并過(guò)程中需要額外的內(nèi)存來(lái)存儲(chǔ)臨時(shí)數(shù)組。

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

1. 穩(wěn)定，因?yàn)樵乇３制湎鄬?duì)順序。

2. 即使對(duì)于大型數(shù)據(jù)集，時(shí)間復(fù)雜度也是 O (n log n)。

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

缺點(diǎn) -

1. 時(shí)間復(fù)雜度 - O(n2)，對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)非常高。
2. 合并過(guò)程需要額外的內(nèi)存。
3. 未到位，因?yàn)樾枰~外的內(nèi)存。
4. 對(duì)于大多數(shù)數(shù)據(jù)集來(lái)說(shuō)通常比??快速排序慢。

應(yīng)用程序 -

1. 用于數(shù)據(jù)太大而無(wú)法放入內(nèi)存的情況，例如合并大文件。
2. 它用于對(duì)鏈表進(jìn)行排序，因?yàn)椴恍枰S機(jī)訪問(wèn)。

5. 快速排序

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

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

時(shí)間復(fù)雜度：

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

• 在已經(jīng)排序的數(shù)組中選擇最小的元素作為主元。

• 選擇最大元素作為按降序排序的數(shù)組中的主元。

O( log n ) - 在除法階段的每一步，數(shù)組大小減半。

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

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

空間復(fù)雜度：

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

2. 最壞情況 - O(n) - 對(duì)于遞歸堆棧。

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

1. 對(duì)于大型數(shù)據(jù)集非常有效，除非樞軸選擇不當(dāng)。
2. 它是緩存友好的，因?yàn)槲覀冊(cè)谕粋€(gè)數(shù)組上進(jìn)行排序，并且不將數(shù)據(jù)復(fù)制到任何輔助數(shù)組。
3. 在不需要穩(wěn)定性時(shí)，用于大數(shù)據(jù)的最快通用算法之一。

缺點(diǎn) -

1. 時(shí)間復(fù)雜度 - O(n2)，對(duì)于大型數(shù)據(jù)集來(lái)說(shuō)非常高。
2. 不穩(wěn)定，因?yàn)樗荒芫S持相等元素的相對(duì)順序。

應(yīng)用程序 -

1. 它用于編程庫(kù)和框架。例如-Python的sorted()函數(shù)和Java的Array.sort()基于快速排序。
2. 它通過(guò)在查詢(xún)執(zhí)行期間有效地對(duì)行進(jìn)行排序來(lái)使用 indDatabase 查詢(xún)優(yōu)化。
3. 由于其緩存友好的特性，它非常適合大型數(shù)據(jù)集的內(nèi)存排序。

6.堆排序

堆排序是一種基于比較的排序算法。它是選擇排序的擴(kuò)展。在堆排序中，我們創(chuàng)建一個(gè)二叉堆并將最大或最小元素與最后一個(gè)元素交換。然后，我們將堆大小減少 1。重復(fù)此過(guò)程，直到堆的長(zhǎng)度大于 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)程構(gòu)建最大堆。 Heapify 是一種用于維護(hù)二叉堆數(shù)據(jù)結(jié)構(gòu)的堆屬性的方法。
2. 如果數(shù)組大小為 n，則包含 n//2 個(gè)父節(jié)點(diǎn)。
3. 對(duì)于索引 i 處的父級(jí)：

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

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

1. 迭代所有父級(jí)從索引 n//2 到 0 的子樹(shù)，并對(duì)它們調(diào)用 heapify 函數(shù)。
2. 現(xiàn)在，數(shù)組成為最大堆，最大元素位于索引 0。
3. 將堆的第一個(gè)元素與最后一個(gè)元素交換，并將堆的大小減少 1。
4. 重復(fù)這個(gè)過(guò)程，直到堆的長(zhǎng)度大于1

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

O( log n ) - 創(chuàng)建最大堆

O(n) - 創(chuàng)建最大堆并且交換元素 n 次。

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

空間復(fù)雜度：對(duì)于所有情況 - O(log n) - 對(duì)于遞歸堆棧。

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

1. 即使對(duì)于大型數(shù)據(jù)集，時(shí)間復(fù)雜度也是 O (n log n)。
2. 內(nèi)存使用率幾乎恒定。

缺點(diǎn) -

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

應(yīng)用程序 -

1. 對(duì)于實(shí)現(xiàn)頻繁提取最大或最小元素的優(yōu)先級(jí)隊(duì)列非常有用。
2. 在需要就地排序且內(nèi)存使用至關(guān)重要的系統(tǒng)中很有用。
3. 用于需要排名的場(chǎng)景。

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

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

基數(shù)排序使用計(jì)數(shù)排序作為子例程。它將計(jì)數(shù)排序應(yīng)用于數(shù)字的每個(gè)數(shù)字位并重復(fù)排序，直到處理完數(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ù)字的長(zhǎng)度為 d，則在數(shù)組上調(diào)用計(jì)數(shù)排序 d 次。

2. 對(duì)數(shù)組中的每個(gè)數(shù)字位置調(diào)用計(jì)數(shù)排序，從個(gè)位開(kāi)始，然后是十位，依此類(lèi)推。

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

• 首先，創(chuàng)建一個(gè)索引數(shù)組，并根據(jù)元素的值映射元素。例如，如果數(shù)字為 4，則在索引數(shù)組的第 4 個(gè)索引處遞增值。
• 從索引數(shù)組創(chuàng)建前綴和數(shù)組。
• 使用前綴和數(shù)組，創(chuàng)建一個(gè)等于輸入數(shù)組長(zhǎng)度的新排序數(shù)組
• 例如，如果前綴和數(shù)組在索引 1 處的值為 2，則將值 1 放置在排序數(shù)組中的位置 2 處，并將前綴和數(shù)組中的值遞減 1

時(shí)間復(fù)雜度：

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

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

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

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

空間復(fù)雜度：對(duì)于所有情況 - O(n k)，其中 n 是輸入數(shù)組的長(zhǎng)度，k 是索引數(shù)組中的值的范圍。

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

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

缺點(diǎn) -

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

應(yīng)用程序 -

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

以上是排序算法 ||蟒蛇 ||數(shù)據(jù)結(jié)構(gòu)和算法的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！