Java数据结构之选择排序算法的实现与优化

选择排序算法的原理

选择排序是一种简单直观的排序算法，它的基本思想是：从待排序的数据中选出最小的数，将其放在首位；再从剩余的数据中选出最小的数，放在已排序数据的末尾；以此类推，直到所有数据均已排序完毕。

选择排序的时间复杂度为O(n²)，空间复杂度为O(1)。相比于其他排序算法，选择排序的代码实现简单、易于理解。

选择排序算法的实现

下面是选择排序算法的Java实现：

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

其中，外层循环用于控制排序次数，内层循环用于查找未排序数据中的最小值并记录其位置，然后将它和第i个元素交换位置。

选择排序算法的优化

尽管选择排序算法的时间复杂度为O(n²)，但它依然可以通过一些优化技巧来提高效率，比如：

1. 最小值和最大值一起获取：每次在遍历数组时，记录当前遍历的位置和数组中最小值和最大值的位置。当遍历结束时，将最小值和最大值放置在数组两端。
2. 减少交换次数：每次找到最小值后，将其和第i个元素交换位置时，可以使用一个变量j记录最小值的位置，最后再和第i个元素交换位置。

下面是基于这些优化技巧的Java实现：

public static void advancedSelectionSort(int[] arr) {
    int len = arr.length;
    int minIndex, maxIndex, temp;
    for (int i = 0; i < len / 2; i++) {
        minIndex = i;
        maxIndex = i;
        for (int j = i + 1; j < len - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        if (maxIndex == i) {
            maxIndex = minIndex; // 防止maxIndex和minIndex重复
        }
        if (maxIndex != len - i - 1) {
            temp = arr[len - i - 1];
            arr[len - i - 1] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
}

示例说明

下面是一个使用选择排序算法对整型数组进行排序的示例：

int[] arr = new int[] { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
selectionSort(arr);
System.out.println(Arrays.toString(arr));
// 输出：[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

这段代码首先创建了一个包含11个元素的整型数组，然后使用选择排序算法对其进行排序，最后输出排序结果。

下面是使用优化后的选择排序算法对整型数组进行排序的示例：

int[] arr = new int[] { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
advancedSelectionSort(arr);
System.out.println(Arrays.toString(arr));
// 输出：[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

这段代码与前一个示例大致相同，只是使用了优化后的选择排序算法进行排序。