Python排序算法——选择排序

时间:2023-02-08 23:10:14

有趣的事,Python永远不会缺席!

如需转发,请注明出处:小婷儿的python https://www.cnblogs.com/xxtalhr/p/10787340.html

一、选择排序(Selection sort)

  选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,所以称为:选择排序。

1、原理

    1.   设第一个元素为比较元素,依次和后面的元素比较,比较完所有元素找到最小的元素,将它和第一个元素互换
    2.  重复上述操作,我们找出第二小的元素和第二个位置的元素互换,以此类推找出剩余最小元素将它换到前面,即完成排序

2、举例

      举个例子,假设我现在有一个数列需要使用冒泡来排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22],

     我们来看看使用冒泡的详细步骤:

      1、首先11作为比较元素和列表后面的所有元素比较,找到最小的11,并放在第一位,第一轮完了,列表

        是  [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]

      2、然后,99作为比较元素,和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比较,找到最小的11,

        和第二位元素99交换位置,即第二轮比较完后,列表为   [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]

      3、第三轮比较完,22最小,和第三个元素33交换位置,列表变为  [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]

      4、最终得到列表  [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

注:是一轮比较完后,找出最小的,再交换这个元素和对应轮数位置处的元素位置,每轮只交换一次。二冒泡排序是,没比较一次,就交换一次位置,每轮要交换很多次。

二、代码

  代码用jupyternotebook实现

  实现思路: 使用双重for循环,内层变量为i, 外层为j,在内层循环中不断的比较相邻的两个值(j, j+1)的大小,如果j+1的值大于j的值,交换两者位置,每循环一次,外层的i增加1,等到i等于(len(arr) - 1)的时候,结束循环

  第一次看不懂很正常,不要灰心,下面是 jupyter 使用代码的实现

 def selection_sort(arr):
"""选择排序"""
# 第一层for表示循环选择的遍数
for i in range(len(arr) - 1):
# 将起始元素设为最小元素
min_index = i
# 第二层for表示最小元素和后面的元素逐个比较
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
# 如果当前元素比最小元素小,则把当前元素角标记为最小元素角标
min_index = j
# 查找一遍后将最小元素与起始元素互换
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr selection_sort([11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22])
#返回结果 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

三、特点

    

  选择排序冒泡排序很类似,但是选择排序每轮比较只会有一次交换,而冒泡排序会有多次交换,交换次数比冒泡排序少,就减少cpu的消耗,所以在数据量小的时候可以用选择排序,实际适用的场合非常少

  1. 比较性:因为排序时元素之间需要比较,所以是比较排序

  2. 稳定性:因为存在任意位置的两个元素交换,比如[5,  8, 5, 2],第一个5会和2交换位置,所以改变了两个5原来的相对顺序,所以为不稳定排序

  3. 时间复杂度:我们看到选择排序同样是双层循环n*(n-1)),所以时间复杂度也为:O(n^2)

  4. 空间复杂度:只需要常数个辅助单元,所以空间复杂度也为O(1)

  5. 记忆方法:选择对象要先选最小的,因为嫩,哈哈

结果   

  Successfully !!!

  有趣的事,Python永远不会缺席!还不来加我,瞅什么瞅。

Python排序算法——选择排序