首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

【算法实践】有始有终,雨露均沾--手把手带你手撸选择排序

前言

选择排序是一个非常经典且简单直观的排序算法,无论什么数据进去都是 O(n^2) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。其排序时,元素交换次数最差的情况为 n−1 次。选择排序的原理是先固定每个元素的位置,在序列中找到最小的元素,将这个元素与第一个元素交换位置,其次是除去第一个元素,找到剩余序列中最小的元素,与第二个元素交换位置,以此类推,直到所有的元素排完,就能实现选择排序,所以说选择排序是有始有终,雨露均沾的一个算法,哈哈~

选择排序的基本思想是:每一趟在 n−i+1 ( i = 1 , 2 , . . . , n − 1 ) 个元素中选择最小的元素,并将其作为有序序列中第 i 个元素。也就是从头至尾扫描序列,找出最小的一个元素,和第一个元素交换,接着从剩下的元素中继续这种选择和交换方式,最终得到一个有序序列。

所以具体的操作就是:选择排序在开始的时候,先扫描整个列表,以找到列表中的最小元素,然后将这个元素与第一个元素进行交换。这样最小元素就放到它的最终位置上。然后,从第二个元素开始扫描,找到 n-1 个元素中的最小元素,然后再与第二个元素进行交换。以此类推,直到第 n-1 个元素(如果前 n-1 个元素都已在最终位置,则最后一个元素也将在最终位置上)。接下来我们按步骤来厘清它的操作:

算法步骤

  1. 定义一个数组序列,获取序列长度 length
  2. 首先在未排序序列中找到最小元素,存放到排序序列的起始位置。也就是把找到的最小元素和序列中的第一个元素交换位置。
  3. 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。
  4. 以此类推,重复第三步,直到所有元素均排序完毕。
  5. 输出排序结果

操作流程

选择排序很简单,就是很执着地在找最小元素,整个流程如下图:

动图演示

这是在网上找到的一张动图演示,很生动,很直观展现了选择排序的整个过程,

选择排序就是通过数据移动实现的,如果有的元素已经在正确的位置上(即是已经排好序),则不会发生数据的交换,如果发生数据交换,那么两个元素至少有一个被交换到正确的位置上,所以,对 n 个元素进行选择排序。最多交换 n-1 次。

算法实现

方法 1:

1.输入一个待排序的列表 arr = [6,5,2,9,8]

代码语言:javascript
复制
arr = [6,5,2,9,8] 
print('待排序数组:',arr)

代码语言:javascript
复制
length = len(arr)
for i in range(length):
    print("第{i}轮排序".format(i=i+1))
    for j in range(length):
        if arr[j] > arr[i]:
            arr[i], arr[j] = arr[j], arr[i]
    print(arr)

print("完成排序的数组:", arr)

执行结果:

方法 2:减少的交换操作

代码语言:javascript
复制
def selectSort(arr):
    for i in range(len(arr) - 1):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        #当i不是最小元素时,将i和最小的元素进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
        
        #记录排序步骤
        print("第{i}轮排序".format(i=i + 1))
        print(arr)

    return arr
arr1 = [6,5,2,9,8]
print("完成排序的数组:",selectSort(arr1))

执行结果:

总结

选择排序使用了线性查找来寻找最小值,因此在第一轮中需要比较 n-1 个元素,第二轮需要比较 n-2 个元素,直到第 n-1 轮时就只需要比较一个元素,所以,总的比较次数和冒泡排除相同,都是(n-1)+(n-2)+...+1=n^2/2 次;每轮交换元素的次数最多为 1 次,如果输入的数据就是按从小到大排列的,那就无需进行任何交换,选择排序的时间复度也和冒泡排序一样,都是 O(n^2)

  • 发表于:
  • 本文为 InfoQ 中文站特供稿件
  • 首发地址https://www.infoq.cn/article/a098de57a631045b590c943c4
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券