排序算法--直接选择排序

前提：

        选择排序：选择排序(Selection sort)是一种比较简单的排序算法。它的算法思想是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

  话不多说，直接放图：

​

这里每次找到最小的那个元素，将其与未排序序列的第一个元素交换，交换后最小的那个元素已经找到，再从未排序序列中找第二小的元素......直到序列完全有序。

直接选择排序： 

          直接选择排序，顾名思义，直接选择最小或最大的数。它的思想完全契合选择排序的思想，这里就不再过多赘述。

 直接排序的过程：​

手敲的代码： 

​ 

这里我们的思路就是定义一个变量begin，作为未排序序列的第一个数，定义一个变量mini保存最小数的下标。然后从第begin+1个数开始遍历整个序列，如果找到比a[mini]还小的数，就将mini更新为该数的下标。遍历完后就将mini位置的数交换到begin处。最小数确定后，begin++；再遍历剩下的序列，找第二小的数.......直到完全有序。

​

有没有觉得这样每循环一次仅选一个数出来有点浪费？不如我们直接一次选两个数怎么样？

微调版直接选择排序代码分析：

  根据我们上面的分析，改动版的的代码就是一次完成最大、最小两个数的排序，实际上与一个数的排序并没有什么不同。 

 依旧是手敲代码：

 ​

这里无非是多定义了两变量，end与maxi。end控制尾部的变化。一次交换完成后，序列找到最大值和最小值，begin++，end--；继续找未排序序列里的最大值和最小值。

运行代码也是没什么问题。但是，我们一直用一组数据测也没啥意思，换下面这组组数据玩玩：

有没有发现不一样了？我们的排序是完全不正确。

遇事不决，调试代码：

1、                                                                  2、

3、                                                                4、

有没有看出问题？

     我们的最大的数是13，第一次交换时最小值a[6]=0与a[0]=13交换后，最大值的下标maxi还是0。导致后面最大值和end交换的就不是最大值！更要命的，一次交换完，begin和end收缩，a[0]与a[10]的位置已经固定，无法再改动，导致程序越运行越错。

     找到了问题，方法就会有：因为第一次与a[0]交换的一定是最小值(这里的特殊错误是因为begin里放的是整个序列的最大值导致的)，所以我们可以加个判断：

当最大值碰巧在begin位置上，交换了最小值后就将maxi更新到mini的位置(如上图就是maxi从下标为0更新到下标为6的位置)。以此来防止最大值的丢失。

直接选择排序的时间复杂度：

 时间复杂度为铁铁的O(n^2)，最好是直接有序为O(n);

直接选择排序的是不稳定的排序：

注意到上面演示排序过程中两个6的变化了吗？

很明显两个6的位置发生了变化，因此是不稳定的排序。