选择排序

今天我们来聊一下同样比较基础的排序算法-选择排序。选择排序是一种非常直观的排序算法,复杂度为 $O(n^2)$O(n2),和前面介绍的两种算法一样不需要额外的空间。

1. 选择排序算法原理

选择排序的思路是最容易想到的:首先遍历一次列表,找到列表中的最小值,交换到第一个位置; 接下来从第二个位置开始遍历列表,找到最小值,交换到第二个位置上。如此执行下去,直到遍历操作走最后一位上时停止。此时,列表已经完成排序。

2. 选择排序算法过程分析

从上面的算法过程可以看到,该算法的时间复杂度是比较固定的,每次遍历都是比较剩余所有数据,因此其时间复杂度(包括最好、最坏情况和平均)均为 $O(n^2)$O(n2);而空间复杂度则为 $O(1)$O(1),我们只需要一个临时变量保存每次遍历的最小值即可。下面来看一个选择排序的一个示例图:
图片描述

算法的过程差不多已经理清楚了,接下来我们实现这样的排序算法,同样会分成两种数据结构的实现:数组和链表。

图片描述

2. 选择排序的 Python 实现

2.1 数组版的选择排序

对于数组版的选择排序,实现的代码如下:

def choose_sort(nums):
 """
 选择排序
 """
 for i in range(len(nums) - 1):
 min_val = nums[i]
 # 标记最小值位置
 k = i
 for j in range(i + 1, len(nums)):
 # 每次遍历,找到本轮剩余元素的最小值,同时记录相应位置
 if nums[j] < min_val:
 min_val = nums[j]
 k = j
 # 每次遍历数组后找到最小值,交换当前位置与本轮最小值的位置
 if k != i:
 nums[i], nums[k] = nums[k], nums[i]

2.2 链表版的选择排序

同样,对于链表版的选择排序,我们需要用示意图来描述下这个选择排序的过程,这样才能更好帮助我们实现代码。
图片描述

依据上面的示意图,我们给出如下链表的选择排序方法。其中,各个变量的说明在示意图中已有体现,且代码中也给出了部分注释,帮助大家更好理解算法过程。

def choose_sort_link(head):
 """
 排序链表
 """
 first = head
 while first.next:
 p = first
 min_val = p.val
 # 指向最小节点的位置
 k = p
 while p:
 if p.val < min_val:
 min_val = p.val
 k = p
 p = p.next
 # 交换最小位置和遍历的起始位置的值
 first.val, k.val = min_val, first.val
 first = first.next 
 return head

这个对链表排序的题目在 leetcode 上也是有的,题号为148。我使用该代码进行了测试,发现无法通过最后得测试,这并非代码实现问题,而是题目本身的效率要求。后续读者可以使用其他排序算法来完成对链表的排序,通过该题题解。

图片描述

3. 小结

今天的内容比较简单,选择排序在理解上比冒泡排序还要直观和简单,同样前三节排序算法的平均时间复杂度都是 $O(n^2)$O(n2),后面我们会介绍两类非常经典和高效的排序算法,尤其是快速排序算法,几乎代表了排序算法中的最优解,也是各个笔试和面试常考的知识点。

Tips:文中动图制作参考:https://visualgo.net/zh/sorting。