【考研】数据结构考点——直接选择排序

​前言

本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解、博主一只小山猪经典算法篇章学习所得心得、笔记整理和总结。

选择排序的基本思想：每一趟从待排序的记录中选出关键字最小的记录，按顺序存放在已排序的记录序列的最后，直到全部排完为止。

选择排序的主要两种方法：简单选择排序、堆排序。

本文内容主要针对简单选择排序（Simple Selection Sort，即直接选择排序）。在本文最后的练习的中，以举例子说明该排序方法，配以图文，讲解详细。

可搭配以下链接一起学习：

【考研】数据结构考点——希尔排序_住在阳光的心里的博客-CSDN博客

【考研】数据结构考点——直接插入排序_住在阳光的心里的博客-CSDN博客

【考研复习：数据结构】查找（不含代码篇）_住在阳光的心里的博客-CSDN博客

【考研】《数据结构》知识点总结.pdf_考研数据结构知识点总结背诵-其它文档类资源-CSDN文库

目录

​前言

一、算法步骤

二、算法描述

三、算法分析及算法特点

（一）算法分析

（二）算法特点

四、练习

一、算法步骤

1、设待排序的记录存放在数组 r[1...n] 中。第一趟从 r[1] 开始，通过 n - 1 次比较，从n个记录中选出关键字最小的记录，记为 r[k]，交换 r[1] 和 r[k]。

2、第二趟从 r[2] 开始，通过 n - 2 次比较，从 n - 1 个记录中选出关键字最小的记录，记为 r[k]，交换 r[2] 和 r[k]。

3、依次类推，第 i 趟从 r[i] 开始，通过 n - i 次比较，从 n - i + 1 个记录中选出关键字最小的记录，记为 r[k] ，交换 r[i] 和 r[k] 。

4、经过 n - 1 趟，排序完成。

二、算法描述

//对顺序表 L 做简单选择排序
void SelectSort (SqList &L)
{
    for(i = 1; i < L.length; ++i){    //在L.r[i..L.length]中选择关键字最小的记录
        k = i;
        for (j = i+1; j <= L.length; ++j){
            if(L.r[j].key < L.r[k].key) 
                k = j;    //k指向此趟排序中关键字最小的记录
        }
 
        if (k != i){   //交换r[i]与r[k]
            t = L.r[i]; 
            L.r[i] = L.r[k]; 
            L.r[k] = t;
        }
    }
}

三、算法分析及算法特点

（一）算法分析

1、时间复杂度

简单选择排序过程中，所需进行记录移动的次数较少。

最好情况(正序)：不移动；最坏情况(逆序)：移动 3(n - 1) 次。

然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为

因此，简单选择排序的时间复杂度也是 ​。

2、空间复杂度

同冒泡排序一样，只有在两个记录交换时需要个辅助空间， 所以空间复杂度为 ​。
 

（二）算法特点

1、就选择排序方法本身来讲，它是一种稳定的排序方法，但就 “五、练习” 中的第一题排序过程图示所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用“交换记录” 的策略所造成的，改变这个策略。可以写出不产生 “不稳定现象” 的选择排序算法。（考试中，简单选择排序是不稳定的。）

2、可用于链式存储结构。

3、移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。从上述可见，选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序应从如何减少 “ 比较 ” 出发考虑。显然，在 n 个关键子中选出最小值，至少要进行 n - 1 次比较。

然而，继续在剩余的 n - 1 个关键字中选择次小值并非定要进行 n - 2 次比较，若能利用前 n - 1 次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。

简单选择排序算法	比较次数	移动次数
	​	​

按此思想，可以引出树形选择排序，即锦标赛排序，是一种按照锦标赛的思想进行选择排序的思想。之后，为改进，也引出了堆排序（它是树形选择排序的一种）。可见链接：

【考研】数据结构考点——堆排序（含408真题）_住在阳光的心里的博客-CSDN博客

四、练习

1、已知待排序记录的关键字序列为{49, 38, 65, 97, 49, 13, 27, 76}，给出用简单选择排序方法进行排序的过程。

解：简单选择排序过程如下图所示：

​

​​

​

​

​​

 七趟排序后，最后直接选择排序结果为13，27，38，49，49，65，76，97。

 2、从未排序序列中挑选元素，并将其依次插入已排序序列（初始为空）末端的方法，称为（    D    ）

A. 归并排序                B. 冒泡排序                C. 插入排序                D. 选择排序

 3、设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按一下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是（     D     ）
A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序
B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序
C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序
D. 先按 k2 进行简单选择排序，再按 k1 进行直接插入排序

解：可以举例联系思考：

“学生基本信息”（学生1，学生2，学生3，……，学生n）为一个线性表。

每个学生为一个数据元素，包含了姓名，年龄两个数据项。

假设 K1 为姓名，K2 为年龄。

（1）确定 K1 和 K2 的排序顺序。

若先排 K1 再排 K2，则可能出现 K1 顺序不满足小的元素在前，大的在后的结果，不符合题意，排除 A、C 选项。

所以，K2 排好序后，再对 K1 排序。

（2）考虑算法稳定性。

针对选项B，先按 k2 进行直接插入排序，k2 值小的在前，大的在后。再按 k1 进行简单选择排序，因为简单选择排序是不稳定的，则对于 K1 相同而 K2 不同的元素可能会改变相对次序，不一定符合题意。

只能选 D。

稳定的算法：

通俗地讲就是，能保证排序前两个相等的数其在序列的前后位置顺序与排序后它们的前后位置顺序一致。

形式化解释如下：一列数中，如果Ai = Aj，Ai 位于 Aj 的前置位，那么经过升降序排序后Ai 仍然位于 Aj 的前置位。

参考：

排序算法稳定性和不稳定性的理解 - 自己有自己的调调、 - 博客园 (cnblogs.com)

​