选择排序：简单高效的选择

大家好，今天我们来聊聊选择排序（Selection Sort）算法。这是一个非常简单的排序算法，适合用来学习排序的基本思路和操作。选择排序在许多排序算法中以其直观和易于实现的特点著称，虽然它的效率不如其他高效算法（如快速排序和归并排序），但它仍然是学习和理解排序算法的一个很好的起点。

一、什么是选择排序？

选择排序是一种简单的排序算法，其基本思想是每次从未排序的部分中选出最小的元素，将它与未排序部分的第一个元素交换位置。这样，每一轮选择都会将一个最小元素放到数组的前面，直到整个数组排序完成。

选择排序的步骤：

1. 从数组的第一个元素开始，假设当前元素为最小值。
2. 从剩余的未排序部分中，找到最小的元素。
3. 如果找到的最小元素小于当前元素，交换它们的位置。
4. 将未排序部分的最小元素交换到当前元素的位置。
5. 继续对剩余部分进行选择排序，直到整个数组有序。

二、选择排序的工作原理

假设我们有一个数组 [64, 34, 25, 12, 22, 11, 90]，我们来演示一下选择排序的过程：

1. 第一轮选择：

   • 假设 64 是最小的元素，遍历数组的剩余部分，找到最小值 11，与 64 交换，得到 [11, 34, 25, 12, 22, 64, 90]。

2. 第二轮选择：

   • 假设 34 是最小的元素，遍历剩余部分，找到最小值 12，与 34 交换，得到 [11, 12, 25, 34, 22, 64, 90]。

3. 第三轮选择：

   • 假设 25 是最小的元素，遍历剩余部分，找到最小值 22，与 25 交换，得到 [11, 12, 22, 34, 25, 64, 90]。

4. 第四轮选择：

   • 假设 34 是最小的元素，遍历剩余部分，找到最小值 25，与 34 交换，得到 [11, 12, 22, 25, 34, 64, 90]。

5. 第五轮选择：

   • 假设 34 是最小的元素，遍历剩余部分，找到最小值 34，不需要交换，得到 [11, 12, 22, 25, 34, 64, 90]。

6. 第六轮选择：

   • 假设 64 是最小的元素，遍历剩余部分，找到最小值 64，不需要交换，得到 [11, 12, 22, 25, 34, 64, 90]。

7. 第七轮选择：

   • 最后剩下的元素是 90，它已经排到最后，不需要交换。

最终排序后的数组为 [11, 12, 22, 25, 34, 64, 90]。

三、选择排序的时间复杂度

选择排序的时间复杂度是 O(n²)，其中 n 是数组的元素数量。原因如下：

• 每一轮需要遍历未排序部分的所有元素，找到最小的元素并交换它。第一轮遍历需要 n-1 次比较，第二轮需要 n-2 次比较，依此类推，总共需要 n(n-1)/2 次比较。
• 由于这是一种双重循环结构，因此其时间复杂度为 O(n²)。

最好情况：

• 即使数组已经有序，选择排序仍然会进行完整的遍历，时间复杂度仍然是 O(n²)。

最坏情况：

• 当数组是逆序时，选择排序依然需要进行完整的遍历，时间复杂度为 O(n²)。

四、选择排序的空间复杂度

选择排序是原地排序算法，它只需要常数级的额外空间来存储临时变量（用于交换元素）。因此，它的空间复杂度为 O(1)。

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

public static void selectsort(int[] arr) {int index = 0;int max = arr[index];for (int j = 0; j < arr.length - 1; j++) {//循环一次选择一个最大值for (int i = 1; i < arr.length - j; i++) {index = arr[i] > max ? i : index;max = arr[index];}//交换最大值与未排序元素的最后一个swap(arr, index, arr.length - j - 1);//注意重置最大值与索引index = 0;max = arr[index];}}public static void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}

输入数组 {64, 34, 25, 12, 22, 11, 90}，程序的输出是：

11 12 22 25 34 64 90