选择排序算法原理

发布时间：2023-06-28 14:19:47 所属栏目：教程来源：

导读：今天我们来聊一下同样比较基础的排序算法-选择排序。选择排序是一种非常直观的排序算法。

1. 选择排序算法原理

选择排序的思路是最容易想到的：首先遍历一次列表，找到列表中的最小值，交换到第一个位置；接下

今天我们来聊一下同样比较基础的排序算法-选择排序。选择排序是一种非常直观的排序算法。

1. 选择排序算法原理

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

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

2. 选择排序的 Python 实现
2.1 数组版的选择排序
对于数组版的选择排序，实现的代码如下：

def choose_sort(nums):
"""
选择排序
"""
for i in range(len(nums) - ):
min_val = nums[i]
# 标记最小值位置
k = i
for j in range(i + , 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。我使用该代码进行了测试，发现无法通过最后得测试，这并非代码实现问题，而是题目本身的效率要求。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!