Java選擇排序演算法的實作與效能最佳化技巧

Java選擇排序法程式碼的完整實作及最佳化技巧

選擇排序（Selection Sort）是一種簡單直覺的排序演算法，其基本想法是找到未排序數組中的最小（或最大）元素，並將其放在已排序數組的末尾。重複這個步驟直到整個陣列排序完成。以下是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};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

在上述程式碼中，我們首先定義了選擇排序的主要方法selectionSort(int[] arr)。在主方法中，我們先計算陣列的長度，然後透過兩個巢狀的循環來尋找未排序部分中的最小元素，並將其與目前位置的元素進行交換。重複這個步驟直到整個陣列排序完成。最後，在main方法中，我們定義了一個範例數組，並呼叫了selectionSort方法進行排序。

選擇排序的時間複雜度是O(n^2)，這意味著隨著元素數量的增加，排序所需的時間將呈現二次方層級成長。但是，我們可以透過一些技巧來提高選擇排序的效率。

最佳化技巧1：減少交換操作次數

在選擇排序的每一輪中，我們都會找到未排序部分的最小元素，並將其與目前位置的元素交換。儘管這是必要的，但如果每次交換都需要進行三次賦值操作，可能會影響效能。我們可以透過直接記錄最小元素的索引值，然後只進行一次賦值運算來減少交換次數。修改後的程式碼如下所示：

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;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

優化技巧2：新增檢查已排序部分的判斷

在每一輪中，我們都會遍歷未排序部分以找到最小元素。但是，如果在遍歷過程中發現已排序部分的最大元素比未排序部分的最小元素還要小，那麼排序已經完成了，我們可以提前終止排序過程。修改後的程式碼如下所示：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            boolean sorted = true;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] < arr[j-1]) {
                    sorted = false;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

透過上述最佳化技巧，我們可以讓選擇排序的執行效率提高。

總結：

選擇排序是一種簡單但效率較低的排序演算法。透過減少交換操作的次數和新增已排序部分的判斷，可以提高選擇排序的效率。然而，儘管選擇排序的時間複雜度為O(n^2)，在某些特定場景中它仍然是一個有效的排序演算法。

希望本文能對你理解並實現選擇排序，並透過一些最佳化技巧來提高演算法效率有所幫助。

以上是Java選擇排序演算法的實作與效能最佳化技巧的詳細內容。更多資訊請關注PHP中文網其他相關文章！