图文讲解选择排序算法的原理及在Python中的实现

yipeiwu_com6年前Python基础

基本思想:从未排序的序列中找到一个最小的元素,放到第一位,再从剩余未排序的序列中找到最小的元素,放到第二位,依此类推,直到所有元素都已排序完毕。假设序列元素总共n+1个,则我们需要找n轮,就可以使该序列排好序。在每轮中,我们可以这样做:用未排序序列的第一个元素和后续的元素依次相比较,如果后续元素小,则后续元素和第一个元素交换位置放到,这样一轮后,排在第一位的一定是最小的。这样进行n轮,就可排序。

原理图
图1:

201654103109156.gif (288×288)

图2:

201654103139716.gif (723×224)

初始数据不敏感,不管初始的数据有没有排好序,都需要经历N2/2次比较,这对于一些原本排好序,或者近似排好序的序列来说并不具有优势。在最好的情况下,即所有的排好序,需要0次交换,最差的情况,倒序,需要N-1次交换。

数据交换的次数较少,如果某个元素位于正确的最终位置上,则它不会被移动。在最差情况下也只需要进行N-1次数据交换,在所有的完全依靠交换去移动元素的排序方法中,选择排序属于比较好的一种。

python代码实现:

def sort_choice(numbers, max_to_min=True):
 """
 我这没有按照标准的选择排序,假设列表长度为n,思路如下:
  1、获取最大值x,将x移动到列最后。[n1, n2, n3, ... nn]
  2、将x追加到排序结果[n1, n3, ... nn, n2]
  3、获取排序后n-1个元素[n1, n3, ... nn],重复第一步,重复n-1次。

 max_to_min是指从大到小排序,默认为true;否则从小到大排序。
 对[8, 4, 1, 0, 9]排序,大致流程如下:
 sorted_numbers = []
 [8, 4, 1, 0, 9], sorted_numbers = [9]
 [4, 1, 0, 8], sorted_numbers = [9, 8]
 [1, 0, 4], sorted_numbers = [9, 8, 4]
 [0, 1], sorted_numbers = [9, 8, 4, 1]
 [0], sorted_numbers = [9, 8, 4, 1, 0]
 """
 if len(numbers) <= 1:
  return numbers
 sorted_list = []
 index = 0
 for i in xrange(len(numbers) - index):
  left_numbers = _get_left_numbers(numbers, max_to_min)
  numbers = left_numbers[:-1]
  sorted_list.append(left_numbers[-1])
  index += 1
 return sorted_list

def _get_left_numbers(numbers, get_max=True):
 '''
 获取最大值或者最小值x,并且将x抽取出来,置于列表最后.
 Ex: get_max=True, [1, 4, 3] ⇒ [1, 3, 4] 
  get_max=False, [1, 4, 3] ⇒ [4, 3 ,1] 
 '''
 max_index = 0
 for i, num in enumerate(numbers):
  if get_max:
   if num > numbers[max_index]:
    max_index = i
  else:
   if num < numbers[max_index]:
    max_index = i
 numbers = numbers[:max_index] + numbers[max_index + 1:] + [numbers[max_index]]
 return numbers

测试一下:

>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=True)
[0, 4, 0, 31, 9, 19, 67, 89]
>>> get_left_numbers([0, 4, 0, 31, 9, 19, 89,67], get_max=False)
[4, 0, 31, 9, 19, 89, 67, 0]

>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=False)
[0, 0, 4, 9, 19, 31, 67, 89]
>>> sort_choice([0, 4, 0, 31, 9, 19, 89,67], max_to_min=True)
[89, 67, 31, 19, 9, 4, 0, 0]

相关文章

python微信跳一跳系列之棋子定位像素遍历

python微信跳一跳系列之棋子定位像素遍历

前言 在前几篇博客中,分别就棋子的颜色识别、模板匹配等定位方式进行了介绍和实践,这一篇博客就来验证一下github中最热门的跳一跳外挂中采用的像素遍历的方法。 方法说明 像素遍历的实质依...

浅谈python中截取字符函数strip,lstrip,rstrip

浅谈python中截取字符函数strip,lstrip,rstrip

一、起因 今天在做角色控制中,有一个地方用到rstrip,判断用户请求的url是否与数据库对应可用权限中url相符。 if request.path == x.url or reques...

python django框架中使用FastDFS分布式文件系统的安装方法

python django框架中使用FastDFS分布式文件系统的安装方法

一、安装FastDFS 1-1:执行docker命令安装 # 安装tracker docker run -dti --network=host --name tracker -v /...

Python turtle画图库&&画姓名实例

Python turtle画图库&&画姓名实例

*****看一下我定义的change()和run()函数****** 绘图坐标体系: 作用:设置主窗体的大小和位置 turtle.setup(width, height, sta...

python文件操作的简单方法总结

文件操作1 #文件操作流程:1、打开文件,得到一个文件句柄;通过文件句柄操作文件;关闭文件。 #将文件打开文件赋给file1,test_file为文件名,utf-8为文件编码;fil...