汉码未来

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]
代码块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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
代码块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

3. 小结

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