java常见算法 选择排序

选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是每一轮从未排序的元素中选择最小（或最大）的元素，将其放置在已排序部分的末尾。具体步骤如下：

1. 找到数组中最小（或最大）的元素，将其与数组的第一个元素交换位置，将该元素视为已排序部分的末尾。
2. 在剩余的未排序部分中，再次找到最小（或最大）的元素，将其与数组的第二个元素交换位置，将该元素视为已排序部分的末尾。
3. 重复上述步骤，每一轮选择未排序部分的最小（或最大）元素，并将其放置到已排序部分的末尾，直到整个数组有序。

下面是使用Java实现的选择排序算法：

public 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;
    }
}

在上述代码中，arr是待排序的数组。外层循环用于选择已排序部分的末尾，从第一个元素开始，到倒数第二个元素结束。内层循环用于在未排序部分中寻找最小元素的下标。每一轮选择结束后，将找到的最小元素与已排序部分的末尾元素进行交换，将该元素纳入已排序部分。

选择排序的时间复杂度始终为O(n^2)，无论数组的初始状态如何。尽管选择排序的时间复杂度较高，但在某些情况下仍可用于简单排序任务。然而，对于大规模的乱序数组，更高效的排序算法如快速排序和归并排序通常更为合适。

原文链接：codingdict.net