首页 前端知识 排序算法--直接选择排序

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

2024-05-19 09:05:00 前端知识 前端哥 525 417 我要收藏

前提:

        选择排序:选择排序(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的位置发生了变化,因此是不稳定的排序。

转载请注明出处或者链接地址:https://www.qianduange.cn//article/8853.html
评论
会员中心 联系我 留言建议 回顶部
复制成功!