Java怎么实现选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。选择排序的时间复杂度为O(n²)，因此它适用于数据量较小的场景。

选择排序的基本步骤

1. 初始化：假设数组的第一个元素为最小元素。
2. 查找最小元素：遍历未排序部分，找到最小元素的位置。
3. 交换元素：将最小元素与未排序部分的第一个元素交换位置。
4. 重复：重复上述步骤，直到所有元素都排序完成。

Java实现选择排序

下面是一个使用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};

        System.out.println("排序前的数组:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

代码解析

1. selectionSort方法：

   • n 是数组的长度。
   • 外层循环从第一个元素开始，遍历到倒数第二个元素。
   • 内层循环从当前元素的下一个元素开始，遍历到数组末尾，查找最小元素的位置。
   • 找到最小元素后，将其与当前元素交换位置。

2. main方法：

   • 初始化一个整数数组 arr。
   • 调用 selectionSort 方法对数组进行排序。
   • 使用 printArray 方法打印排序前后的数组。

输出结果

运行上述代码，输出结果如下：

排序前的数组:
64 25 12 22 11 
排序后的数组:
11 12 22 25 64 

选择排序的优缺点

优点

• 简单易懂：选择排序的实现逻辑简单，容易理解和实现。
• 空间复杂度低：选择排序是原地排序算法，不需要额外的存储空间。

缺点

• 时间复杂度高：选择排序的时间复杂度为O(n²)，在处理大规模数据时效率较低。
• 不稳定：选择排序是一种不稳定的排序算法，可能会改变相同元素的相对位置。

总结

选择排序是一种基础的排序算法，虽然它的时间复杂度较高，但在某些特定场景下（如数据量较小或对内存要求较高）仍然有其应用价值。通过本文的示例代码，你可以轻松地在Java中实现选择排序，并理解其工作原理。