选择排序

选择排序（Selection Sort）

工作原理

选择排序是一种简单直观的排序算法。它的基本思想是通过不断地选择未排序部分的最小（或最大）元素，并将其放到已排序部分的末尾。

1. 初始状态：数组的一部分被视为已排序，另一部分被视为未排序。
2. 寻找最小元素：从未排序部分找出最小（或最大）的元素。
3. 交换元素：将找到的最小元素与未排序部分的第一个元素交换。
4. 重复步骤2-3：直到所有元素都被排序。

Java实现

public class SelectionSort {

    /**
     * 选择排序算法
     * @param arr 要排序的数组
     */
    public static 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);
        }
    }

    /**
     * 交换数组中的两个元素
     * @param arr 数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 打印数组中的元素
     * @param arr 数组
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    /**
     * 主函数
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        int[] sampleArray = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(sampleArray);

        sort(sampleArray);

        System.out.println("Sorted array:");
        printArray(sampleArray);
    }
}

代码解析

1. sort() 方法：这是选择排序的核心实现。它接受一个整型数组作为参数，并对其进行排序。
2. 外层循环：从数组的第一个元素开始，逐步处理未排序部分。
3. 内层循环：从未排序部分找出最小元素的索引。
4. 交换操作：将找到的最小元素交换到已排序部分的末尾。
5. swap() 方法：用于交换数组中的两个元素。
6. printArray() 方法：用于打印数组中的元素。
7. main() 方法：测试排序功能的方法。

注意事项

• 时间复杂度：选择排序的平均和最坏情况下的时间复杂度均为 O(n^2)，其中 n 是数组长度。
• 稳定性：选择排序是不稳定的排序算法，因为在排序过程中，相等的元素可能会改变它们原有的顺序。
• 空间复杂度：选择排序的空间复杂度为 O(1)，因为它不需要额外的存储空间。

适用场景

选择排序适合于小规模数据的排序，或者在内存受限的情况下使用。然而，由于其较高的时间复杂度，不建议在大规模数据集中使用选择排序。

希望这段代码及其说明能够帮助您更好地理解和实现选择排序算法。如果您有任何疑问或需要进一步的帮助，请随时告诉我。