Python 实现经典算法之选择排序 python中的选择排序算法

off999 2024-12-26 15:54 47 浏览 0 评论

前言

前面我们已经一起学习了冒泡排序（Python 实现经典算法之冒泡排序），这篇文章，大家与好奇心就一起再来看看选择排序吧。

简介

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n2) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾（这里注意，是已排序好的末尾，不是数组末尾！）。以此类推，直到全部待排序的数据元素的个数为零。可以理解为一个 0 到 n-1 的迭代，每次向后查找选择一个最小的元素。选择排序是不稳定的排序方法。

步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
重复步骤 2，直到所有元素均排序完毕。

动图演示

实例代码

###
# author: 今日头条：技术好奇心
###

# 选择排序例子
def selection_sort(arr):
    # 按数组总长度来，依次遍历
    for i in range(len(arr) - 1):
        # 存储最小下标值(这里默认假设数组第一个为最小值)
        min_index = i
        # 以 j 为下标，i+1为起始位置，再次对数组进行遍历
        # （因为之前的以及是最小值排序好了，所以起始为i+1）
        for j in range(i + 1, len(arr)):
            # 如果这个数小于之前记录的最小数，则更新最小数的下标
            if arr[j] < arr[min_index]:
                min_index = j
        # 将 i 位置的数（前面已排序序列的末尾的数）和最小数进行交换
        arr[i], arr[min_index] = arr[min_index], arr[i]
        # 这里为了方便大家对比参考，所以每次比较完了就打印一次
        print(arr)


# 执行
if __name__ == '__main__':
    # 建立演示数组
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    # 执行排序方法
    selection_sort(arr)
    # 看看比较完之后数组的样子
    print('-------------------- 技术好奇心 -------------------')
    print(arr)

运行结果：

[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
-------------------- 技术好奇心 -------------------
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

从上面的结果来看，排序是成功的。

里面为了方便大家观看对比，我将每次的执行结果也打印出来了。

从过程中可以看出，排序是从数组第一个开始的，然后逐渐通过遍历比较往后替换排序。