了解選擇排序演算法（附Java範例）

選擇排序：逐步指南

選擇排序是一種簡單的排序演算法。 它反覆從清單的未排序部分中找到最小元素並將其放在開頭。這個過程一直持續到整個清單被排序為止。

選擇排序的工作原理

讓我們用一個例子來說明，按升序對這個陣列進行排序：

迭代 1：

目標是將最小的元素放在開頭。我們首先假設第一個元素是最小值。

我們將當前最小值與每個後續元素進行比較，如果找到更小的元素，則更新最小值。

這將持續到確定實際的最小值。

最後，我們將最小元素與第一個元素交換。

第一個元素現已排序。 後續迭代將僅考慮未排序的部分。

後續迭代：

對每個剩餘的未排序元素重複此過程。

演算法迭代 n-1 次（其中 n 是數組的長度）。 第五次迭代後（對於六元素數組），最後一個元素被隱式排序。

選擇排序實作（Java）：

import java.util.Arrays;

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

輸出：

未排序數組：[8,2,6,4,9,1] 排序數組：[1, 2, 4, 6, 8, 9]

複雜性分析：

• 時間複雜度： 所有情況下都是 O(n²)（最佳、平均、最差）。 無論輸入順序為何，巢狀迴圈總是執行固定次數。
• 空間複雜度： O(1)。 這是一種就地演算法，需要恆定的額外空間。

結論：

選擇排序的 O(n²) 時間複雜度使其對於大型資料集效率低下。 它最適合小型陣列或簡單性優先於性能的情況。

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