選擇排序演算法

什麼是選擇排序？

選擇排序演算法將陣列分為兩部分：已排序部分和未排序部分。最初，已排序部分為空，未排序部分包含所有元素。此演算法的工作原理是從未排序部分中找到最小（或最大，取決於排序順序）元素，並將其與未排序部分的第一個元素交換。這個過程一直持續到整個陣列被排序為止。

演算法步驟

1. 從陣列中的第一個元素開始，並假設它是最小的。
2. 將此元素與陣列中的其他元素進行比較。
3. 如果找到較小的元素，請將其與第一個元素交換。
4. 移動到陣列中的下一個元素，並對剩餘的未排序元素重複此過程。
5. 繼續這個過程，直到整個陣列排序完畢。

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

通過 1：

• 索引 0 和陣列其餘部分之間的最小元素是 11。
• 我們將 64 換成 11。

第一遍後的陣列：[11, 25, 12, 22, 64]

透過2：

• 現在，專注於從索引 1 開始的子數組。 25、12、22、64 之間的最小元素是 12。
• 我們用 12 交換 25。

第二遍後的陣列：[11, 12, 25, 22, 64]

通過 3：

• 25、22、64 之間的最小元素是 22。
• 我們用 22 交換 25。

第三遍後的陣列：[11, 12, 22, 25, 64]

第 4 關：

• 子數組現在包含 25、64。由於它們已經按順序排列，因此不需要交換。

最終排序數組：[11, 12, 22, 25, 64]

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted part
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

排序數組：[11, 12, 22, 25, 64]

選擇排序的時間複雜度：

• 最佳情況：O(n²)

• 平均狀況：O(n²)

• 最壞情況：O(n²)

儘管選擇排序對於小型資料集表現良好，但對於較大的陣列來說並不理想，因為它的時間複雜度為 O(n²)。然而，它很容易實現，並且在需要考慮記憶體的情況下非常有用，因為選擇排序是就地的（不需要額外的記憶體）。

優點和缺點

優點：

• 易於理解和實作。

• 在小列表上表現良好。

• 不需要額外的內存，因為它對數組進行排序。

缺點：

• 由於 O(n²) 時間複雜度，對於大型資料集效率較低。

• 它不是一個穩定的排序演算法，這意味著相等的元素可能無法保留它們相對於彼此的順序。

以上是選擇排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！