选择排序算法及其实现与分析

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序的部分的末尾。选择排序的时间复杂度为 (O(n^2))，适合小规模数据的排序。

选择排序的步骤

1. 初始化：从数组的第一个元素开始，假设它是最小值。
2. 遍历未排序部分：遍历数组中未排序的部分，找到最小值。
3. 交换：将找到的最小值与当前元素交换位置。
4. 重复：对下一个未排序的元素重复步骤 1 到 3，直到整个数组排序完成。

选择排序的代码示例

下面是一个用 Java 实现的选择排序的示例代码：

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

        // 遍历数组
        for (int i = 0; i < n - 1; i++) {
            // 假设当前索引 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[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = 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 value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

代码分析

1. 方法定义：selectionSort(int[] arr) 是选择排序的实现，接受一个整数数组作为参数。
2. 外层循环：for (int i = 0; i < n - 1; i++) 遍历数组的每个元素，直到倒数第二个元素。
3. 内层循环：for (int j = i + 1; j < n; j++) 遍历未排序部分，寻找最小值。
4. 条件判断：if (arr[j] < arr[minIndex]) 检查当前元素是否小于当前最小值，如果是，则更新最小值的索引。
5. 交换操作：如果找到的最小值的索引与当前索引不同，则进行交换。
6. 打印数组：printArray(int[] arr) 是一个辅助方法，用于打印数组的内容。

选择排序的优缺点

优点：

• 实现简单，易于理解。
• 不需要额外的存储空间（原地排序）。

缺点：

• 时间复杂度为 (O(n^2))，在大规模数据时效率较低。
• 不稳定排序，可能会改变相同元素的相对顺序。

选择排序适合用于小规模数据的排序，或者在对算法的学习和理解上有很好的帮助。