java怎么實現選擇排序

Java怎么實現選擇排序

選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的基本思想是：每次從未排序的部分中選擇最?。ɑ蜃畲螅┑脑?，將其放到已排序部分的末尾。選擇排序的時間復雜度為O(n2)，因此它適用于數據量較小的場景。

選擇排序的基本步驟

1. 初始化：假設數組的第一個元素為最小元素。
2. 查找最小元素：遍歷未排序部分，找到最小元素的位置。
3. 交換元素：將最小元素與未排序部分的第一個元素交換位置。
4. 重復：重復上述步驟，直到所有元素都排序完成。

Java實現選擇排序

下面是一個使用Java實現選擇排序的示例代碼：

public class SelectionSort {

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

        // 遍歷數組
        for (int i = 0; i < n - 1; i++) {
            // 假設當前索引為最小元素的位置
            int minIndex = i;

            // 在未排序部分查找最小元素
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 將最小元素與未排序部分的第一個元素交換
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};

        System.out.println("排序前的數組:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("排序后的數組:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

代碼解析

1. selectionSort方法：

   • n 是數組的長度。
   • 外層循環從第一個元素開始，遍歷到倒數第二個元素。
   • 內層循環從當前元素的下一個元素開始，遍歷到數組末尾，查找最小元素的位置。
   • 找到最小元素后，將其與當前元素交換位置。

2. main方法：

   • 初始化一個整數數組 arr。
   • 調用 selectionSort 方法對數組進行排序。
   • 使用 printArray 方法打印排序前后的數組。

輸出結果

運行上述代碼，輸出結果如下：

排序前的數組:
64 25 12 22 11 
排序后的數組:
11 12 22 25 64 

選擇排序的優缺點

優點

• 簡單易懂：選擇排序的實現邏輯簡單，容易理解和實現。
• 空間復雜度低：選擇排序是原地排序算法，不需要額外的存儲空間。

缺點

• 時間復雜度高：選擇排序的時間復雜度為O(n2)，在處理大規模數據時效率較低。
• 不穩定：選擇排序是一種不穩定的排序算法，可能會改變相同元素的相對位置。

總結

選擇排序是一種基礎的排序算法，雖然它的時間復雜度較高，但在某些特定場景下（如數據量較小或對內存要求較高）仍然有其應用價值。通過本文的示例代碼，你可以輕松地在Java中實現選擇排序，并理解其工作原理。