系列文章目录
第六篇：【排序算法】⑥快速排序：Hoare、挖坑法、前后指针法-CSDN博客
目录
前言
直接选择排序比较简单，实现起来较容易，但是直接选择排序与直接插入排序的区别难以理清，笔者下方整理一个表格供参考。
一、直接选择排序是什么？
算法思想
直接选择排序的思想是：
每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。 通过不断选择剩余元素中的最小者来实现排序。
直接选择排序为什么能实现排序？
很好理解，假设i=0是数组下标，n是数据个数。直接选择排序就是简单粗暴的从未排序的数据集中挑出最小/最大，放在第i个位置处，i++，未排序的数据个数就变成n-i个，重复直到i==n-1（数组下标）。
二、实现直接选择排序
博主这里以升序为例：
void SelectionSort(int* a, int n)
{
if (!a)return;
for (int i = 0; i < n; ++i)
{
int _min = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[_min])_min = j;
}
swap(&a[i], &a[_min]);
}
}
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}依据算法，从数据集中，挑选处特征码最小/最大的数据放在已排序的末尾。
①_min变量用于存储合适数据的下标。从第i号，到之后的未排数据中选择最小或最大的数据，_min保存其下标，等内循环结束交换数据值；
②外循环，每一次循环的目的是在未排数据中寻找最小/最大的值；内循环，作用是依次拿未排数据与a[i]比较大小。
三、分析直接选择排序
直接选择排序的特征
1. 直接选择排序非常好理解，但是效率不是很好，故实际中很少使用；
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定。
与直接插入排序的区别
直接选择排序与直接插入排序的区别是什么？
直接选择排序： 每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。 通过不断选择剩余元素中的最小者来实现排序。
直接插入排序： 将未排序部分的元素逐个插入到已排序部分的适当位置。 即，将元素插入到已排序序列中的正确位置，从而逐步构建有序序列。
| 特性 | 直接选择排序 | 直接插入排序 |
|---|---|---|
| 基本思想 | 在未排序序列中选择最小元素放入已排序序列末尾 | 将未排序元素插入已排序序列的合适位置 |
| 操作核心 | 选择 + 交换 | 比较 + 移位 |
| 时间复杂度 | 永远 O(n²)（任何情况） | 平均 O(n²)，但有序时最优 O(n) |
| 空间复杂度 | O(1)（原地） | O(1)（原地） |
| 稳定性 | 不稳定（交换破坏顺序） | 稳定（保持相同元素顺序） |
| 数据敏感性 | 无关数据分布（固定比较次数） | 强相关（有序数据效率飙升） |
| 交换/移动次数 | 交换次数少（n-1次） | 移动次数多（需整体移位） |
总结
本文是【排序算法】系类第三篇，直接选择排序较为简单故篇幅较短。
来不及怀念直接选择排序了，接下来登场的是常用且效率高、结构较复杂的另一种选择排序算法：堆排序！