排序(5):简单选择排序

2017年12月27日10:57:46 18 12,122 °C
摘要

简单选择排序是一种选择排序。

排序(5):简单选择排序

一、前言

简单选择排序是一种选择排序

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

二、算法思想

简单排序很简单,它的大致处理流程为:

  • 从待排序序列中,找到关键字最小的元素;
  • 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
  • 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。

动态效果示意图:

排序(5):简单选择排序

举例说明,处理过程示意图如下所示:

排序(5):简单选择排序

如图所示,每趟排序中,将当前 i 小的元素放在位置 i 上。

1、代码

C++:

 

运行结果:

排序(5):简单选择排序

Python:

运行结果同上。

三、算法分析

1、简单算法排序性能

排序(5):简单选择排序

其中,N2为N^2。

2、时间复杂度

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数总是N (N - 1) / 2

而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0.

当序列反序时,移动次数最多,为3N (N - 1) /  2。

所以,综合以上,简单排序的时间复杂度为 O(N^2)

3、空间复杂度

简单选择排序需要占用 1 个临时空间,用于保存最小值得索引。

 

本站整理自:

http://www.cnblogs.com/jingmoxukong/p/4303289.html

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:18   其中:访客  9   博主  9

    • avatar 明明是我先的 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 电信 2

      temp = sorted_list[i]
      sorted_list[i] = sorted_list[min_index]
      sorted_list[min_index] = temp
      我把这段代码封装了一下
      def sort_swap(a,b):
      tmp = a
      a = b
      b = tmp
      ,为什么结果就不对了??

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

          @明明是我先的 调用sort_swap之后,你看数据交换了吗?得改变sort_list列表的值啊。

            • avatar 明明是我先的 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 电信 2

              @Jack Cui 是的呢我之前是这样的 sort_swap(sort_list[min_index],sort_list[i]),
              改成sort_list[min_index],sort_list[i] = sort_swap(sort_list[min_index],sort_list[i])就可以了
              额,想复杂了,算了

          • avatar 夹饼豆浆 来自天朝的朋友 谷歌浏览器 Windows 10 贵州省毕节地区 联通 1

            你好,你这里写到的“而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0.”,我认为选择排序运行时间不受输入序列的影响,即便是序列正序,移动次数还是需要自己和自己进行一次移动操作,从而不论序列是怎样的,移动次数都为N

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                @夹饼豆浆 有关的,如果真序,只需要比对,但无需移动。这个移动的意思是交换两个元素的位置。

                  • avatar 夹饼豆浆 来自天朝的朋友 谷歌浏览器 Windows 10 贵州省毕节地区 联通 1

                    @Jack Cui 正序的情况下,内部循环结束后,不是仍然要进行一次交换的操作吗?

                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 东北大学大学生城

                        @夹饼豆浆 哦哦,是代码有问题,应该加个if判断,过会儿修改下。感谢。

                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                          @夹饼豆浆 已更正。

                    • avatar chris_33 来自天朝的朋友 谷歌浏览器 Windows 7 广东省广州市海珠区 /荔湾区电信 3

                      师兄,我这里是选择这样子弄,用break会直接退出循环~
                      if min_index == i:
                      continue
                      sorted_list[i],sorted_list[min_index]=sorted_list[min_index],sorted_list[i]

                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 黑龙江省哈尔滨市 联通

                          @chris_33 不过你这是continue吧。python支持这么赋值。

                            • avatar chris_33 来自天朝的朋友 QQ浏览器  1505-A01 Build/MRA58K 广东省广州市 移动 3

                              @Jack Cui 我是用的continue来的😂表达失误

                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 黑龙江省哈尔滨市 联通

                                  @chris_33 continu没有跳出循环啊。只是跳出来当前循环。

                                    • avatar chris_33 来自天朝的朋友 谷歌浏览器 Windows 7 广东省广州市海珠区 /荔湾区电信 3

                                      @Jack Cui 你换下数组,用[50, 123, 543, 187, 49, 30, 0, 2, 11, 100],就会知道错在哪里了,我可能表达不太准确了

                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通

                                  @chris_33 哦哦,get已更正,感谢。

                                    • avatar chris_33 来自天朝的朋友 谷歌浏览器 Windows 7 广东省广州市海珠区 /荔湾区电信 3

                                      @Jack Cui 互相学习~

                                  • avatar youyounow 来自天朝的朋友 谷歌浏览器 Windows 10 江苏省南京市 南京理工大学 1

                                    稳定性为什么是不稳定呢?每次找到最小值,相同的取前面一个,相对位置没有发生改变啊

                                      • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                                        @youyounow 按照找最小值,与无序区首部交换的思想则不稳定:
                                        排序前:
                                        2,4,4*,3
                                        排序后:
                                        2,3,4*,4