5.8. 选择排序¶

5.8. The Selection Sort

中文英文

选择排序通过在每次遍历列表时只进行一次交换来改进冒泡排序。为了实现这一点，选择排序在遍历时会寻找最大值，并在完成遍历后将其放置在正确的位置。与冒泡排序类似，第一次遍历后，最大项已经放在了正确的位置。第二次遍历后，第二大的项也会放在正确的位置。这个过程会持续进行，并且需要 \(n - 1\) 次遍历来排序 \(n\) 个项，因为在第 \((n - 1)\) 次遍历后，最后一个项必须已经到位。

图 3 显示了选择排序的完整排序过程。在每次遍历中，选择剩余部分中最大的项，然后将其放置在其正确的位置。第一次遍历放置了 93，第二次遍历放置了 77，第三次遍历放置了 55，依此类推。函数的实现见 ActiveCode 1。

活动: 5.8.1 选择排序
def selection_sort(a_list):
    for i, item in enumerate(a_list):
        min_idx = len(a_list) - 1
        for j in range(i, len(a_list)):
            if a_list[j] < a_list[min_idx]:
                min_idx = j
        if min_idx != i:
            a_list[min_idx], a_list[i] = a_list[i], a_list[min_idx]


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

有关更多细节，CodeLens 3 允许您逐步分析算法。

追踪选择排序
def selection_sort(a_list):
    for i, item in enumerate(a_list):
        min_idx = len(a_list) - 1
        for j in range(i, len(a_list)):
            if a_list[j] < a_list[min_idx]:
                min_idx = j
        if min_idx != i:
            a_list[min_idx], a_list[i] = a_list[i], a_list[min_idx]
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

您可能会发现选择排序的比较次数与冒泡排序相同，因此它的时间复杂度也是 \(O(n^{2})\)。然而，由于交换次数的减少，选择排序在基准测试中通常执行得更快。实际上，对于我们的列表，冒泡排序进行了 20 次交换，而选择排序仅进行了 8 次。

自我检测

假设你有以下数字列表需要排序：

[11, 7, 12, 14, 19, 1, 6, 18, 8, 20] 哪个列表表示选择排序经过三次完整遍历后的部分排序列表？

选项 a: [7, 11, 12, 1, 6, 14, 8, 18, 19, 20]
选项 b: [7, 11, 12, 14, 19, 1, 6, 18, 8, 20]
选项 c: [11, 7, 12, 14, 1, 6, 8, 18, 19, 20]
选项 d: [11, 7, 12, 14, 8, 1, 6, 18, 19, 20]

正确答案: d

反馈 a: 选择排序类似于冒泡排序（您似乎做了这个），但使用了更少的交换。
反馈 b: 这看起来像是插入排序。
反馈 c: 这个选项看起来类似于正确答案，但数字被移动到左边以腾出位置，而不是进行交换。
反馈 d: 选择排序通过减少交换次数来改进冒泡排序。

The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place. This process continues and requires \(n - 1\) passes to sort \(n\) items, since the final item must be in place after the \((n - 1)\)-th pass.

Figure 3 shows the entire sorting process for the selection sort. On each pass, the largest remaining item is selected and then placed in its proper location. The first pass places 93, the second pass places 77, the third places 55, and so on. The function is shown in ActiveCode 1.

Activity: 5.8.1 Selection Sort
def selection_sort(a_list):
    for i, item in enumerate(a_list):
        min_idx = len(a_list) - 1
        for j in range(i, len(a_list)):
            if a_list[j] < a_list[min_idx]:
                min_idx = j
        if min_idx != i:
            a_list[min_idx], a_list[i] = a_list[i], a_list[min_idx]


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

For more detail, CodeLens 3 allows you to step through the algorithm.

Tracing the Selection Sort
def selection_sort(a_list):
    for i, item in enumerate(a_list):
        min_idx = len(a_list) - 1
        for j in range(i, len(a_list)):
            if a_list[j] < a_list[min_idx]:
                min_idx = j
        if min_idx != i:
            a_list[min_idx], a_list[i] = a_list[i], a_list[min_idx]
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

You may see that the selection sort makes the same number of comparisons as the bubble sort and is therefore also \(O(n^{2})\). However, due to the reduction in the number of exchanges, the selection sort typically executes faster in benchmark studies. In fact, for our list, the bubble sort makes 20 exchanges, while the selection sort makes only 8.

Self Check

Suppose you have the following list of numbers to sort:

[11, 7, 12, 14, 19, 1, 6, 18, 8, 20] which list represents the partially sorted list after three complete passes of selection sort?

answer a: [7, 11, 12, 1, 6, 14, 8, 18, 19, 20]
answer b: [7, 11, 12, 14, 19, 1, 6, 18, 8, 20]
answer c: [11, 7, 12, 14, 1, 6, 8, 18, 19, 20]
answer d: [11, 7, 12, 14, 8, 1, 6, 18, 19, 20]

correct: d

feedback a: Selection sort is similar to bubble sort (which you appear to have done) but uses fewer swaps
feedback b: This looks like an insertion sort.
feedback c: This one looks similar to the correct answer but instead of swapping the numbers have been shifted to the left to make room for the correct numbers.
feedback d: Selection sort improves upon bubble sort by making fewer swaps.

最后更新: 2024年9月13日
创建日期: 2024年9月9日