【java实现+4种变体完整例子】排序算法中【选择排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

以下是选择排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：

一、选择排序基础实现

原理

每一轮遍历未排序部分，找到最小元素并交换到当前起始位置，逐步构建已排序序列。

代码示例

public class SelectionSort {
    void sort(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;
                }
            }
            swap(arr, i, minIndex); // 交换当前元素与最小值
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

复杂度分析

• 时间复杂度：O(n²)（所有情况）。
• 空间复杂度：O(1)。
• 稳定性：不稳定（相同值的元素可能因交换顺序改变相对位置）。

二、常见变体及代码示例

1. 递归实现

改进点：用递归替代循环，代码结构更清晰。
适用场景：教学或代码风格偏好递归。

public class RecursiveSelectionSort {
    void sort(int[] arr, int n) {
        if (n <= 1) return;
        int minIndex = findMinIndex(arr, 0, n);
        swap(arr, 0, minIndex); // 将最小值放到首位
        sort(arr, n - 1); // 递归处理剩余部分
    }

    private int findMinIndex(int[] arr, int start, int end) {
        int minIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2. 双向选择排序（鸡尾酒选择排序）

改进点：每一轮同时找到最小和最大元素，并将它们放到正确的位置。
适用场景：数据分布较分散或两端有序，减少比较次数。

public class CocktailSelectionSort {
    void sort(int[] arr) {
        int n = arr.length;
        int start = 0, end = n - 1;
        while (start < end) {
            int minIndex = start;
            int maxIndex = start;
            for (int i = start; i <= end; i++) {
                if (arr[i] < arr[minIndex]) minIndex = i;
                if (arr[i] > arr[maxIndex]) maxIndex = i;
            }
            // 交换最小值到起始位置
            swap(arr, minIndex, start);
            // 处理最大值交换（避免与最小值冲突）
            if (maxIndex == start) swap(arr, maxIndex, minIndex);
            else swap(arr, maxIndex, end);
            start++;
            end--;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. 优化版（减少比较次数）

改进点：通过减少内层循环次数，将比较次数减半。
适用场景：进一步优化基础实现的性能。

public class OptimizedSelectionSort {
    void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            int minIndex = i;
            int maxIndex = n - 1 - i;
            for (int j = i + 1; j <= n - 1 - i; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
                if (arr[j] > arr[maxIndex]) maxIndex = j;
            }
            swap(arr, i, minIndex);
            if (maxIndex == i) swap(arr, maxIndex, minIndex);
            else swap(arr, maxIndex, n - 1 - i);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

三、变体对比表格

四、关键选择原则

1. 基础场景：优先使用基础实现，因其简单且适用于小规模数据。
2. 代码风格：递归实现适合教学或偏好函数式编程的场景，但需注意栈空间开销。
3. 数据分布：双向选择排序在数据分布较分散时效率略高，但实现复杂度增加。
4. 稳定性需求：所有变体均不稳定，若需稳定排序需选择其他算法（如归并排序）。
5. 优化需求：优化版通过减少比较次数，在数据量较大时可略微提升性能。

通过选择合适的变体，可在特定场景下优化代码结构或提升性能（如双向排序减少比较次数），但需权衡实现复杂度与性能收益。