当前位置：首页 > news >正文

java算法：选择排序

news 来源：原创 2024/9/29 14:27:00

文章标题

概述与基本实现
优缺点
尝试优化

概述与基本实现

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，放置在已排序的部分的末尾，直到所有元素都排序完成。

实现步骤：

遍历数组，将当前位置作为最小值的索引（假设为minIndex）。
在未排序部分中遍历数组，从当前位置开始，找到最小值的索引。
将最小值与当前位置的元素交换位置。这样，最小值将会被放置在已排序部分的末尾。
重复步骤2和3，直到整个数组排序完成。

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("原始数组: " + Arrays.toString(arr));selectionSort(arr);System.out.println("排序后数组: " + Arrays.toString(arr));}
}

通过选择排序算法，数组按升序进行了排序。在每次循环中，选择排序会找到未排序部分的最小值，并将其放置在已排序部分的末尾，直到整个数组排序完成。选择排序的时间复杂度为O(n^2)，其中n是数组的大小。

优缺点

优点：

简单直观：选择排序算法的实现相对简单，容易理解和实现。
不占用额外空间：选择排序算法是在原地进行排序的，不需要额外的辅助空间。
稳定性：选择排序是一种稳定的排序算法，不会改变相等元素的相对顺序。

缺点：

时间复杂度：选择排序的时间复杂度为O(n^2)，其中n是数组的大小。在最坏情况下，无论输入数据的顺序如何，都需要进行n*(n-1)/2次比较和n次交换操作。
不适用于大规模数据：由于选择排序的时间复杂度较高，它在处理大规模数据时效率较低，不如其他高效的排序算法（如快速排序、归并排序等）。
不稳定的选择性：尽管选择排序是一种稳定的排序算法，但在选择最小值的过程中，交换操作可能会打破相等元素的相对顺序，导致不稳定性。

选择排序算法在简单性和稳定性方面具有一些优点，但在时间复杂度和适用性上存在一些缺点。对于小规模的数据或者对稳定性要求较高的场景，选择排序可能是一个合适的选择。然而，对于大规模数据或对性能有较高要求的情况，其他更高效的排序算法通常更合适。

尝试优化

优化选择排序的方法：

最小值和最大值同时查找：传统的选择排序算法会先找到最小值的索引，然后进行交换。但实际上，在同一次遍历中，可以同时找到最小值和最大值的索引，然后进行两个位置的交换。这样可以减少一半的比较次数。
减少交换次数：传统的选择排序算法在找到最小值或最大值后会立即进行交换。但可以优化为先记录最小值（或最大值）的索引，然后在一次遍历结束后再进行交换。这样可以减少交换的次数。

示例代码：

public class SelectionSort {public static void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;int maxIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;} else if (arr[j] > arr[maxIndex]) {maxIndex = j;}}// 将最小值交换到已排序部分的开头if (minIndex != i) {int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}// 如果最大值的索引发生了交换，重新调整最大值的索引if (maxIndex == i) {maxIndex = minIndex;}// 将最大值交换到已排序部分的末尾if (maxIndex != n - 1) {int temp = arr[maxIndex];arr[maxIndex] = arr[n - 1];arr[n - 1] = temp;}n--; // 已排序部分增加一个元素，未排序部分减少一个元素}}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组: " + Arrays.toString(arr));selectionSort(arr);System.out.println("排序后数组: " + Arrays.toString(arr));}
}