选择排序¶

字数 481 个代码 217 行图片 1 张阅读时间 4 分钟访问量

一句话解释

每轮从未排序序列中选最小值，与未排序首元素交换，将其纳入已排序序列尾部，直至完全有序。

一、算法图解¶

1.1 Manim 动画演示¶

Manim 动画演示源代码

"""Manim Animation for Selection Sort."""

from __future__ import annotations as _

from math import sqrt
from os import remove
from subprocess import run
from typing import override

from manim import *

GOLDEN_RATIO: float = (sqrt(5) - 1) / 2
RADIUS: float = (1 - GOLDEN_RATIO) / 4
OPACITY: float = (sqrt(5) + 1) / 4

FONT_CHINESE: str = "LXGW WenKai"
FONT_ENGLISH: str = "Comic Mono"

MIDDLE_GRAY: ManimColor = ManimColor.from_rgb((0.5, 0.5, 0.5))


class Manim(Scene):
    """A Scene is the canvas of my animation."""

    @override
    def setup(self) -> None:
        title = Text("选择排序", font=FONT_CHINESE, weight=BOLD, color=MIDDLE_GRAY)
        title.to_edge(UP)
        mark = Text("xiaokang2022.github.io", font=FONT_ENGLISH, font_size=18, color=MIDDLE_GRAY)
        mark.to_corner(DR)
        self.add(title, mark)

    @override
    def tear_down(self) -> None:
        self.wait()

    @override
    def construct(self) -> None:
        data = [4, 6, 3, 2, 7, 1, 5]

        bars = {
            i: (
                Text(
                    f"{v}",
                    font=FONT_ENGLISH,
                    font_size=32,
                    color=MIDDLE_GRAY,
                ),
                RoundedRectangle(
                    RADIUS,
                    fill_opacity=OPACITY,
                    width=GOLDEN_RATIO,
                    height=GOLDEN_RATIO*v,
                    fill_color=BLUE,
                    stroke_color=MIDDLE_GRAY,
                ),

            ) for i, v in enumerate(data)
        }

        for i, (value, rectangle) in bars.items():
            rectangle.move_to(np.array([i-(len(data)/2)+0.5, 0, 0]))
            rectangle.align_to(np.array([0, -2.5, 0]), DOWN)
            value.next_to(rectangle, UP)

            index = Text(
                f"{i}",
                font=FONT_ENGLISH,
                font_size=32,
                color=MIDDLE_GRAY,
            ).next_to(rectangle, DOWN)

            self.add(index, rectangle, value)

        self.wait()

        for i in range(length := len(data)):
            min_index = i
            self.play(bars[i][1].animate.set_fill(RED), run_time=GOLDEN_RATIO)
            for j in range(i + 1, length):
                self.play(bars[j][1].animate.set_fill(YELLOW), run_time=GOLDEN_RATIO)
                if data[j] < data[min_index]:
                    self.play(bars[min_index][1].animate.set_fill(BLUE), run_time=GOLDEN_RATIO)
                    min_index = j
                    self.play(bars[j][1].animate.set_fill(RED), run_time=GOLDEN_RATIO)
                else:
                    self.play(bars[j][1].animate.set_fill(BLUE), run_time=GOLDEN_RATIO)

            data[i], data[min_index] = data[min_index], data[i]

            animations = [m.animate.shift(RIGHT*(min_index-i)) for m in bars[i]]
            animations += [m.animate.shift(LEFT*(min_index-i)) for m in bars[min_index]]
            self.play(*animations, run_time=GOLDEN_RATIO)
            self.play(bars[min_index][1].animate.set_fill(GREEN), run_time=GOLDEN_RATIO)

            bars[i], bars[min_index] = bars[min_index], bars[i]


if __name__ == "__main__":
    config.format = "png"
    config.transparent = True

    Manim().render()

    PATH: str = ".\\media\\images"

    run(
        "ffmpeg "
        "-framerate 60 "
        f"-i {PATH}\\Manim%04d.png "
        "-c:v libwebp_anim "
        "-q 85 "
        "-compression_level 6 "
        "-loop 0 "
        "-preset text "
        "output.webp",
        shell=True,
        check=True,
    )

    frame = 0

    while True:
        try:
            remove(f"{PATH}\\Manim{frame:04d}.png")
        except FileNotFoundError:
            break
        frame += 1

1.2 Mermaid 流程图示意¶

graph TD
    A(("开始")) --> B[/"初始化数组 arr<br>n = len(arr)"/]
    B --> C["i = 0"]
    C --> D{i < n-1?}
    D -- 是 --> E["min_index = i<br>j = i+1"]
    E --> F{j < n?}
    F -- 是 --> G{"arr[j] < arr[min_index]?"}
    G -- 是 --> H["min_index = j"]
    H --> I["j += 1"]
    G -- 否 --> I
    I --> F
    F -- 否 --> J["交换元素<br>arr[i], arr[min_index]"]
    J --> K["i += 1"]
    K --> D
    D -- 否 --> L(("结束"))

    style A fill:#0F07,stroke:#7777
    style L fill:#F007,stroke:#7777

二、算法性质¶

2.1 时间复杂度¶

时间复杂度为 \(O(n^2)\)。

2.2 空间复杂度¶

空间复杂度为 \(O(1)\)。

2.3 其它性质¶

就地性，无额外空间开销
稳定性，与具体实现有关
自适应性
基于比较

三、算法实现¶

3.1 多语言代码¶

下面提供了多种语言的版本，仅供参考。部分编程语言下方提供了可视化代码，但加载可能稍慢，请耐心等待。

🔵 Python🔴 C++🟠 Java🟡 JavaScript🟣 C🟢 C#🔵 Go🟤 Rust

def selection_sort(arr: list[int]) -> None:
    for i in range(len(arr)):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

可视化代码 🔍全屏查看

void selectionSort(std::vector<int> &arr) {
    for (int i = 0, minIndex; i < arr.size(); i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

可视化代码 🔍全屏查看

void selectionSort(ArrayList<Integer> arr) {
    for (int i = 0, minIndex; i < arr.size(); i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr.get(j) < arr.get(minIndex)) {
                minIndex = j;
            }
        }
        Collections.swap(arr, i, minIndex);
    }
}

可视化代码 🔍全屏查看

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
}

可视化代码 🔍全屏查看

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);//(1)!
    }
}

函数 swap 的定义如下：

void swap(int arr[], int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

可视化代码 🔍全屏查看

void SelectionSort(List<int> arr) {
    for (int i = 0, minIndex; i < arr.Count; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.Count; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

非常抱歉！pythontutor 暂时还不支持 C# 的可视化！

func selectionSort(arr []int) {
    for i := 0; i < len(arr); i++ {
        minIndex := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

非常抱歉！pythontutor 暂时还不支持 Go 的可视化！

fn selection_sort(arr: &mut Vec<i32>) {
    for i in 0..arr.len() {
        let mut min_index = i;
        for j in i + 1..arr.len() {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        arr.swap(i, min_index);//(1)!
    }
}

你也可以使用解构赋值 (arr[i], arr[min_index]) = (arr[min_index], arr[i]); 来交换两个变量，但这种方式在性能和安全上不如直接调用方法 swap。

非常抱歉！pythontutor 暂时还不支持 Rust 的可视化！

3.2 自我测试¶

下面是一个 Python 交互式环境，你可以在其中编写自己的代码进行一些测试。初次启动需要较长时间，请耐心等待！

交互式编程 🚀启动环境 ⚡运行

%reset -f

def selection_sort(arr: list[int]) -> None:
    pass

if __name__ == "__main__":
    arr: list[int] = [7, 0, 6, 1, 5, 2, 4, 3]
    selection_sort(arr)
    print(arr)