【排序】选择排序算法

特别说明

对于算法，重在理解其思想、解决问题的方法，思路。因此，以下内容全都假定待排序序列的存储结构为：顺序存储结构。

选择排序思想

选择排序又称为简单选择排序，主要思想描述如下：

01.假设待排序列表为 $R_{1..n}$ 。选择排序将 $R_{1..n}$ 划分为由已排序好序的 $R_{1..m}$ 部分以及未排序的 $R_{m + 1..n}$ 部分；

注意：刚开始时 $R_{1..m}$ 部分其实可认为只有一个元素，即： $R_{1}$ 元素

02.每次从 $R_{m + 1..n}$ 部分中选出最小(或最大)的那个元素，将其放在 $R_{1..n}$ 的末尾位置；

03.重复02步骤，直到 $R_{m + 1..n}$ 部分为空为止；

编码参考

简单选择排序是非常简单的一种排序算法。其编码参考如下：

 1 // 
 2 // summary     : 选择排序
 3 // in param    : seqlist 待排序列表.同时也是排完序列表.
 4 // in param    : nLen 列表长度
 5 // out param   : --
 6 // return      : --
 7 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
 8 //               02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的.
 9 void select_sort(int seqlist[/*nLen*/], const int nLen) {
10     if (nLen <= 1) {
11         return;// only one element.
12     }
13     auto nInnerIdx = 0;
14     auto nMinIdx   = 0;
15     auto nTemp     = 0;
16     for (auto nOuterIdx = 0, nInnerIdx = 0; nOuterIdx < nLen - 1; ++nOuterIdx) {
17         nInnerIdx = nOuterIdx;
18         nMinIdx   = nInnerIdx;
19         while (++nInnerIdx < nLen) {
20             if (seqlist[nInnerIdx] < seqlist[nMinIdx]) {
21                 nMinIdx = nInnerIdx;
22             }
23         }
24         if (nMinIdx != nOuterIdx) {
25             nTemp              = seqlist[nOuterIdx];
26             seqlist[nOuterIdx] = seqlist[nMinIdx];
27             seqlist[nMinIdx]   = nTemp;
28         }
29     }
30 }

简单选择排序算法编码参考

算法分析

简单选择排序算法时间复杂度与插入排序算法、冒泡排序算法一样，都是 $O(N^{2})$ 。辅助空间也一样，也是 $O(1)$ 。但相比插入排序与冒泡排序，选择排序的数据移动操作倒没那么频繁(因为在确定未排序部分的最小(或最大)元素时，我们不需要执行移动操作，只需要用下游标标记即可)。