选择排序

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

1. 选择排序算法原理

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

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

从上面的算法过程可以看到，该算法的时间复杂度是比较固定的，每次遍历都是比较剩余所有数据，因此其时间复杂度（包括最好、最坏情况和平均）均为 $O(n^2)$；而空间复杂度则为 $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)$，后面我们会介绍两类非常经典和高效的排序算法，尤其是快速排序算法，几乎代表了排序算法中的最优解，也是各个笔试和面试常考的知识点。

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