【排序算法】选择排序的全面剖析（含详细图解）
【排序算法】选择排序的全面剖析（含详细图解）
选择排序是一种简单直观的排序算法，虽然在时间复杂度上并非最优，但对于理解排序的基本原理和算法设计思想具有重要意义。本文将对选择排序进行深入解析，包括其原理、实现步骤、时间复杂度分析、空间复杂度分析以及与其他排序算法的比较。
选择排序的原理
选择排序的基本思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。它的工作方式类似于在一堆无序的卡片中，每次挑选出最小的卡片放在最前面，然后在剩下的卡片中继续挑选，依次类推，最终使所有卡片按照从小到大（或从大到小）的顺序排列。
选择排序的实现步骤
简单选择排序（以升序为例）
- 首先，遍历整个数组，找到最小的元素。
- 假设第一个元素是最小的，然后从第二个元素开始逐个与它比较。
- 如果发现有比当前假设的最小元素更小的元素，就更新最小元素的索引。
- 当遍历完整个数组后，将找到的最小元素与数组的第一个元素交换位置。
- 此时，数组的第一个元素就是最小的，已经处于正确的位置。
- 接着，在剩下的未排序元素（从第二个元素开始到最后一个元素）中重复上述步骤。
- 再次遍历剩余元素，找到其中最小的元素，并与剩余元素中的第一个元素（即数组的第二个元素）交换位置。
- 不断重复这个过程
- 每次都将剩余未排序元素中的最小元素放置在已排序部分的末尾，直到整个数组都被排序。
以如下所示的数组为例:
对于已排序列表中的第一个位置，整个列表按顺序扫描。目前存储 14 的第一个位置，我们搜索整个列表，发现 10 是最低值。
所以我们用 10 替换 14。经过一次迭代，10（恰好是列表中的最小值）出现在已排序列表的第一个位置。
对于第二个位置，即 33 所在的位置，我们开始以线性方式扫描列表的其余部分。
我们发现 14 是列表中的第二小值，它应该出现在第二个位置。我们交换这些值。
经过两次迭代，两个最小的值以排序的方式出现在开头。
对数组中的其余项应用相同的过程:
代码实现
以下是用 C 语言实现的简单选择排序代码：
void selectionSort(int arr[], int n) {
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;
}
}
}
示例说明
假设我们有一个数组 [5, 3, 8, 4, 2]，下面是选择排序的具体过程：
- 第一次遍历：
- 初始假设第一个元素
5是最小的，minIndex = 0。 - 从第二个元素
3开始比较，发现3 < 5，更新minIndex = 1。 - 继续比较后面的元素
8、4、2，都比3大。 - 遍历完后，将
3与第一个元素5交换，数组变为[3, 5, 8, 4, 2]。
- 第二次遍历：
- 现在从第二个元素
5开始（因为第一个元素已经排好序），假设5是最小的，minIndex = 1。 - 比较
8、4、2，发现2最小，更新minIndex = 4。 - 将
2与第二个元素5交换，数组变为[3, 2, 8, 4, 5]。
- 第三次遍历：
- 从第三个元素
8开始，假设8是最小的，minIndex = 2。 - 比较
4、5，发现4更小，更新minIndex = 3。 - 将
4与第三个元素8交换，数组变为[3, 2, 4, 8, 5]。
- 第四次遍历：
- 从第四个元素
8开始，假设8是最小的，minIndex = 3。 - 比较
5，5比8小，更新minIndex = 4。 - 将
5与第四个元素8交换，数组变为[3, 2, 4, 5, 8]，此时数组已完全排序。
选择排序的时间复杂度分析
最好情况时间复杂度
在最好情况下，即数组本身就是有序的（升序或降序），选择排序的时间复杂度仍然是 O(n^2)。这是因为无论数组是否有序，每次都需要遍历剩余未排序的元素来找到最小（或最大）元素。虽然在最好情况下，每次找到的最小元素总是已经在正确的位置（即第一个未排序元素就是最小的），但仍然需要进行 n-1 次比较和 n-1 次交换（假设数组有 n 个元素）。比较次数的计算公式为：
交换次数为 n-1，忽略常数系数和低阶项，时间复杂度为 O(n^2)。
最坏情况时间复杂度
在最坏情况下，数组是完全逆序的（升序排序时）或完全正序的（降序排序时）。此时，每次选择最小（或最大）元素都需要遍历整个未排序部分，比较次数和交换次数与最好情况相同，都是 O(n^2)。具体来说，比较次数为：
交换次数为 n-1，所以时间复杂度也是 O(n^2)。
平均情况时间复杂度
平均情况下，选择排序也需要大约 O(n^2) 次比较和 O(n) 次交换。因此，平均时间复杂度同样为 O(n^2)。
选择排序的空间复杂度分析
选择排序是一种原地排序算法，它只需要常数级别的额外空间。在排序过程中，只需要使用一些临时变量来记录最小元素的索引和进行元素交换，不需要额外的数据结构来存储数据。因此，空间复杂度为 O(1)。
选择排序的稳定性分析
选择排序是不稳定的排序算法。稳定性是指在排序过程中，如果两个元素相等，它们在排序后的相对顺序是否会保持不变。在选择排序中，当在未排序部分找到最小元素并与已排序部分的元素交换时，如果有多个相等的最小元素，它们的相对顺序可能会发生改变。
例如，有一个数组 [5, 3, 5', 4, 2]（其中 5' 表示另一个值为 5 的元素），在第一次排序时，会将最小的元素 2 与第一个元素 5 交换，此时 5' 的相对位置就发生了变化。原本 5' 在 5 后面，排序后 5' 可能会在 5 的前面，所以选择排序不稳定。
选择排序与其他排序算法的比较
与冒泡排序比较
- 时间复杂度：
- 选择排序和冒泡排序的时间复杂度在最坏、最好和平均情况下都是 O(n^2)。
- 但是，在实际运行中，选择排序通常会比冒泡排序稍微快一些。这是因为冒泡排序在每一次比较后都可能进行交换操作，而选择排序是在一次遍历完未排序部分找到最小元素后才进行一次交换。
- 稳定性：
- 冒泡排序是稳定的排序算法，而选择排序是不稳定的。
- 代码实现复杂度：
- 两者的代码实现都相对简单，但是冒泡排序的代码可能更容易理解一些，因为它的交换操作是相邻元素之间进行的，比较直观。而选择排序需要记录最小元素的索引，然后进行交换，逻辑上稍微复杂一点。
与插入排序比较
- 时间复杂度：
- 插入排序在最好情况下（数组已经有序）时间复杂度为 O(n)，平均和最坏情况下时间复杂度为 O(n^2)。而选择排序在所有情况下时间复杂度都是 O(n^2)。
- 当数组接近有序时，插入排序的性能会比选择排序好很多，因为插入排序在这种情况下可以很快地将新元素插入到已排序部分的合适位置，而选择排序仍然需要进行大量的比较和交换。
- 稳定性：
- 插入排序是稳定的排序算法，选择排序不稳定。
- 空间复杂度：
- 两者的空间复杂度都是 O(1)，都是原地排序算法。
- 适用场景：
- 如果数据量较小且基本有序，插入排序更合适。如果数据的有序性不确定，且对稳定性没有要求，选择排序可以作为一种简单的选择。
与快速排序比较
- 时间复杂度：
- 快速排序的平均时间复杂度为 O(nlogn)，在最坏情况下时间复杂度会退化为 O(n^2)（当分区极度不平衡时）。选择排序始终是 O(n^2)。
- 因此，在大多数情况下，快速排序比选择排序效率高得多。
- 稳定性：
- 快速排序也是不稳定的排序算法，和选择排序一样。
- 空间复杂度：
- 快速排序的空间复杂度在平均情况下为 O(logn)（由于递归调用需要栈空间），最坏情况下为 O(n)。选择排序的空间复杂度为 O(1)。
- 适用场景：
- 对于大规模数据的排序，快速排序通常是更好的选择，因为它的平均性能更好。但如果对稳定性有要求或者数据量较小，并且不希望使用递归（因为递归可能会导致栈溢出等问题），选择排序可能更合适。
总结
选择排序是一种简单易懂的排序算法，其原理直观，代码实现相对容易。它具有原地排序和时间复杂度始终为 O(n^2) 的特点，适用于数据量较小且对算法效率要求不高的场景。在理解排序算法的基本思想和进行简单数据排序时，选择排序是一个很好的学习和实践案例。