Java 选择排序程序

简介

选择排序（Selection Sort）是一种简单直观的排序算法。在这篇博客中，我们将深入探讨如何在 Java 中实现选择排序。我们不仅会介绍其基本概念，还会展示使用方法、常见实践以及最佳实践，帮助读者全面掌握这一算法在 Java 中的应用。

选择排序基础概念

选择排序的基本思想是在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

例如，对于数组 [5, 3, 8, 2, 1]，选择排序的过程如下： 1. 第一次遍历，找到最小元素 1，与第一个元素 5 交换位置，数组变为 [1, 3, 8, 2, 5]。 2. 第二次遍历，从第二个元素开始找最小元素，找到 2，与第二个元素 3 交换位置，数组变为 [1, 2, 8, 3, 5]。 3. 以此类推，直到数组完全排序。

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;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 1};
        System.out.println("Before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        selectionSort(arr);

        System.out.println("\nAfter sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码说明

selectionSort 方法接收一个整数数组 arr 作为参数。
外层循环控制已排序部分的边界，i 从 0 到 n - 2，因为最后一个元素在前面元素都排序好后自然就处于正确位置。
内层循环用于在未排序部分找到最小元素的索引 minIndex。
如果找到的最小元素索引 minIndex 不等于当前索引 i，则交换这两个元素。
在 main 方法中，我们创建一个示例数组，打印排序前的数组，调用 selectionSort 方法进行排序，然后打印排序后的数组。

常见实践

对不同类型数组排序

选择排序不仅适用于整数数组，也适用于其他类型数组，如浮点数数组、字符串数组等。只需修改比较逻辑即可。例如，对字符串数组按字典序排序：

public class StringSelectionSort {
    public static void selectionSort(String[] 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].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                String temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        String[] arr = {"banana", "apple", "cherry", "date"};
        System.out.println("Before sorting:");
        for (String str : arr) {
            System.out.print(str + " ");
        }

        selectionSort(arr);

        System.out.println("\nAfter sorting:");
        for (String str : arr) {
            System.out.print(str + " ");
        }
    }
}

与其他排序算法结合使用

在某些情况下，可以将选择排序与其他更高效的排序算法（如快速排序、归并排序）结合使用。例如，在数据量较小时使用选择排序，数据量较大时切换到更高效的算法。

最佳实践

优化比较次数

在选择排序中，可以使用一个标志位来减少不必要的交换操作。例如：

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

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            boolean swapped = false;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                    swapped = true;
                }
            }
            if (swapped && minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 1};
        System.out.println("Before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        selectionSort(arr);

        System.out.println("\nAfter sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

适用于特定场景

选择排序适用于数据量较小或对空间复杂度要求较高的场景，因为它只需要一个额外的临时变量用于交换元素，空间复杂度为 O(1)。

小结

选择排序是一种简单且易于理解的排序算法。在 Java 中实现选择排序，我们可以通过基本的循环和比较逻辑对数组进行排序。了解其基础概念、使用方法、常见实践以及最佳实践，能够帮助我们在不同场景下灵活运用这一算法，提高程序的性能和效率。

参考资料

《算法导论》
Oracle Java 官方文档
GeeksforGeeks 相关教程