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

排序演算法

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

演算法 -

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

時間複雜度：

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

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

優點 -

1. 無需額外記憶體。

2. 穩定，因為元素保持其相對順序。

缺點 -

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

應用-

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

2. 選擇排序

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

def selectionSort(a):
    i = 0
    while i



演算法 -


迭代數組並找到最小元素。 
與第一個元素交換位置，指針加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



演算法 -


透過計算中點將陣列分成兩半。 
繼續劃分，直到每個子數組的長度為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 smallest="min(a[i:])" index_of_smallest="a.index(smallest)" a i="i+1" return>



<p><strong>演算法 -</strong></p>

<ol>
<li><p>找出數組中的最大數字並確定其中的位數 (d)。如果數字的長度為 d，則在陣列上呼叫計數排序 d 次。 </p></li>
<li><p>對數組中的每個數字位置呼叫計數排序，從個位開始，然後是十位，依此類推。 </p></li>
<li><p>計數排序：</p></li>
</ol>

<ul>
<li>首先，建立一個索引數組，並根據元素的值來對應元素。例如，如果數字為 4，則在索引數組的第 4 個索引處遞增值。 </li>
<li>從索引陣列建立前綴和陣列。 </li>
<li>使用前綴和數組，建立一個等於輸入數組長度的新排序數組</li>
<li>例如，如果前綴和數組在索引 1 處的值為 2，則將值 1 放置在排序數組中的位置 2 處，並將前綴和數組中的值遞減 1</li>
</ul>

<p><strong>時間複雜度：</strong></p>

<p><strong>計數排序</strong> 的時間複雜度為 O(n k)，其中 n 是要排序的元素數量，k 是值的範圍（索引數組的大小）。此複雜度適用於所有三種情況：最佳、平均和最差。 </p>

<p>這是因為，無論陣列是否已經排序，每次都會遵循相同的步驟。 </p>

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

<p>所以總時間複雜度為 O (d) * O(n k) = O (d * (n k))</p>

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

<p><strong>優點 -</strong></p>

<ol>
<li>由於元素保持其相對順序而穩定。 </li>
<li>如果輸入範圍與輸入數量相同，則計數排序通常比所有基於比較的排序演算法（例如合併排序和快速排序）執行得更快。 </li>
</ol>

<p><strong>缺點 -</strong></p>

<ol>
<li>計數排序不適用於小數值。 </li>
<li>如果要排序的值範圍很大，計數排序效率很低。 </li>
<li>非就地排序演算法，因為它使用額外的空間 O(O(n m))。 </li>
</ol>

<p><strong>應用程式 -</strong></p>

<ol>
<li>它用於計算字串中字元出現次數等應用程式。 </li>
<li>對於對具有大範圍值的整數進行排序非常有用，例如 ID 或電話號碼。 </li>
<li>可以有效地對具有多個鍵的資料進行排序，例如日期或元組。 </li>
</ol>


          

            
        </len>

以上是排序演算法 ||蟒蛇 ||資料結構和演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！