【排序算法】——选择排序

前言

        排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

        排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

简介

        所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于一个排序算法的优劣，我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。什么叫稳定性呢？即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的。

        本篇文章讲述的是排序算法中的选择排序，其中包含了两种排序算法，分别是直接选择排序和堆排序，下面将会一一为大家详细介绍。（用升序进行讲解）

      

基本思想

         选择排序算法的基本思想是为每一个位置选择当前最小的元素。

 1.直接选择排序 

        下面我们首先来看一看直接选择排序算法的动图演示：

        看了上图我们可以得知，直接选择排序算法是首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。 

        直接选择排序算法的思路以及代码都比较简单，有了上述讲解相信大家都已经对其了解了。

 2.堆排序

        直接选择排序是选择排序的一种，但是其时间复杂度很高，在实际应用中效率非常低下，那有没有其他的效率高的选择排序呢？答案当然是有的，那就是堆排序(Heapsort)，堆排序主要借助了我们的数据结构--堆来实现。（若是对堆不了解的可以去阅读我的另一篇文章数据结构--堆）。

        当一个堆是大根堆的时候我们知道堆顶元素永远是整个堆中最大的元素，因此每次取堆顶我们都会得到一个最大值（降序则需要用小根堆），这刚好与我们选择排序算法的基本思想相同。下面我将同图画来给大家进行演示：

        此时堆顶元素是数组中最大的元素，将其与最后一个元素交换位置，并对堆进行调整。

       此时对于 9 这个元素我们可以理解为已经把它从该堆中删除了，此时堆中只剩下4个元素，重复此操作即可完成排序，大家可以根据下方的代码具体了解。

代码实现

 1.直接插入排序

        先看原始代码：

void Select_sort(vector<int>& a)
{int n = a.size();//对于直接选择排序来说，只需要进行n - 1次循环即可for (int i = 0; i < n - 1; i++){int minpos = i;//从i位置开始，遍历其后面的数组，找到最小值for (int j = i + 1; j < n; j++){if (a[j] < a[minpos]){minpos = j;}}//将最小值所处的位置与i位置的值进行交换即可swap(a[i], a[minpos]);}
}

        解析：两次循环即可完成，第一层循环控制需要排序的位置，第二次循环寻找该位置后的最小值。

        对于直接选择排序，我们有一种优化办法，可以使其的时间效率增加一倍，虽说时间复杂度是相同的，杯水车薪，但也是一种思路。 

具体思路：

        第一层循环我们从数组的两端开始遍历；

        第二次循环我们同时寻找其中间的最大值和最小值。

        代码如下：

void Select_sort(vector<int>& a)
{int n = a.size();//数组大小为奇数，最后会处于left == right；当数组大小为偶数时，最后会处于left > right//因此结束条件为left < rightfor (int left = 0, right = n - 1; left < right; left++, right--){int minpos = left;int maxpos = left;//从left位置遍历其后面到right位置之前的数组，找到最小值和最大值for (int i = left + 1; i < right; i++){if (a[i] < a[minpos]){minpos = i;}if (a[i] > a[maxpos]){maxpos = i;}}//此时在交换元素时需要注意一个细节：//当我们将a[right]与a[maxpos]交换时，maxpos位置上之前可能是left的位置，这样在之后的交换会出现问题，因此我们需要进行判断接下来的交换是否还要进行swap(a[right], a[maxpos]);if (a[minpos] < a[left]){swap(a[left], a[minpos]);}}
}

         对于优化后的直接选择排序在最后的交换步骤时的细节需要大家额外注意，大家可以自己用一个倒序数组亲自体验一下，以便有更深刻的体会。

 2.堆排序 

        先看代码：

//向下调整算法
void AdjustDown(vector<int>& a, int parent, int end)
{int child = parent * 2 + 1;while (child < end){if (child + 1 < end && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void Heap_sort(vector<int>& a)
{int n = a.size();//首先进行建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//进行排序for (int i = n - 1; i > 0; i--){swap(a[0], a[i]);AdjustDown(a, 0, i);}
}

        对于堆排序来说，比较重要的地方是当我们在进行排序时，一定要注意当每一次交换完元素后，堆中的数据就会减少一个，因此当我们在自己写向下调整算法时，一定要注意此时堆中的数据个数，不然就会出现错误。 

        注：对于建堆和向下调整算法不了解的朋友可以先去看一看数据结构--堆，里面有较为详细的介绍。

总结

1.时空复杂度

        经过分析我们可以得到直接选择排序的时间复杂度和空间复杂度，两层for循环以及常数个变量，因此

直接选择排序：

        时间复杂度：O（N ^ 2）

        空间复杂度：O（1）

        对于堆排序来说，时间复杂度由建堆操作和排序操作决定，具体的计算过程较为复杂，感兴趣的可以自己搜索一下，这里不再赘述。因此

堆排序：

        时间复杂度：O（NlogN）

        空间复杂度：O（1）

        堆排序算法的总体时间复杂度是 O(n log n)，这是因为建堆之后，还需要进行 n-1 次的排序操作，每次排序操作的时间复杂度是 O(log n)。但是，建堆本身的时间复杂度是线性的，这使得堆排序在某些情况下比其他 O(n log n) 排序算法更高效。 

2.稳定性

        在排序算法中，我们不光要关注算法的时空复杂度，还在看看算法的稳定性，什么是稳定性呢？

稳定性是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

        简单分析我们可以知道选择排序算法是不稳定的。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。（对于直接选择排序以及堆排序都是如此）

直接选择排序： 不稳定

堆排序：            不稳定

尾声

        若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！