---
marp: true
theme: kurzus
paginate: true
footer: 数据结构 · 第 5 周 · 排序 I
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# 数据结构

## 第 5 周 – 排序 I：冒泡排序、选择排序和插入排序

Koczka Ferenc 博士 · 埃斯特哈齐·卡罗伊大学 · 2026

---

## 复习

- <strong>二分查找：</strong>O(log n) – 但只适用于<strong>有序</strong>数组！
- 在数组中移动元素代价很高：插入、删除 <strong>O(n)</strong>
- 字符串比较：<strong>字典序</strong>

### 今天的问题

- 怎样把一个数组排好序？
- 需要多少次比较和移动？
- 什么时候该选哪一种简单排序？

<!--
时间安排：排序问题 10' · 冒泡排序 20' · 选择排序 15' · 插入排序 20' · 比较、稳定性 20' · 小结 5'
-->

---

## 排序问题

<strong>已知：</strong><em>n</em> 个可以比较（≤ 关系）的元素组成的序列。
<strong>任务：</strong>重新排列这些元素，使 A[1] ≤ A[2] ≤ … ≤ A[n]。

### 为什么重要？

- <strong>快速查找：</strong>在有序数组上二分查找 – O(log n)
- <strong>分组：</strong>相等的元素排在一起（重复元素、频率）
- <strong>展示：</strong>按字母排序的名单、排行榜、时间顺序
- 据估计，计算机全部运行时间中有相当一部分花在排序上

---

## 基本概念

- <strong>比较：</strong>考察两个元素的关系（`A[i] < A[j]`） – 排序的主要代价
- <strong>移动 / 交换：</strong>改变元素的位置 – 一次交换是 3 次赋值
- <strong>原地排序：</strong>只需要 O(1) 的额外内存
- <strong>稳定排序：</strong>键相等的元素<strong>保持</strong>原来的相对顺序
- <strong>比较排序：</strong>只通过比较来决定元素的顺序

<div class="doboz">

今天我们学习三种 O(n²) 步的<strong>简单</strong>排序算法。更快的 O(n log n) 方法在第 13 周讲解。

</div>

---

<!-- _class: fejezet -->

# 冒泡排序

---

## 冒泡排序 – 思路

- 遍历数组，比较<strong>相邻</strong>的元素
- 如果顺序不对，就<strong>交换</strong>它们
- 一趟之后<strong>最大</strong>的元素到达数组末尾（它“冒泡”上去）
- 在未排序的部分上重复

![w:1000](kepek/h05_buborek.svg)

---

<!-- _class: kicsi tomor -->

## 冒泡排序 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Procedure BubbleSort(A, n)
  For i ← n down to 2
    swapped ← false
    For j ← 1 to i − 1
      If A[j] > A[j + 1] then
        swap(A[j], A[j + 1])
        swapped ← true
      End if
    End for
    If not swapped then
      exit the loop        // 退出循环
  End for
End procedure
```

</div>
<div>

<span class="cimke java">Java</span>

```java
for (int i = n - 1; i >= 1; i--) {
    boolean swapped = false;
    for (int j = 0; j < i; j++)
        if (a[j] > a[j + 1]) {
            int t = a[j];
            a[j] = a[j + 1];
            a[j + 1] = t;
            swapped = true;
        }
    if (!swapped) break;
}
```

<span class="cimke go">Go</span>

```go
if a[j] > a[j+1] {
    a[j], a[j+1] = a[j+1], a[j]
    swapped = true
}
```

</div>
</div>

---

## 冒泡排序 – 分析

| 情况 | 比较次数 | 交换次数 |
|---|---|---|
| 最好（已经有序） | n − 1 | 0 |
| 最坏（逆序） | n(n − 1) / 2 | n(n − 1) / 2 |
| 平均 | ~ n² / 2 | ~ n² / 4 |

- 步数：<strong>O(n²)</strong> · 在有序数组上，有 `swapped` 标志时：<strong>O(n)</strong>
- <strong>原地</strong>排序，<strong>稳定</strong>（从不交换相等的元素）
- 交换次数 = <strong>逆序对</strong>（顺序错误的元素对）的个数

<div class="doboz figyelem">

实际上它是简单排序中最慢的 – 交换次数太多。

</div>

---

<!-- _class: fejezet -->

# 选择排序

---

## 选择排序 – 思路

- 找出<strong>最小</strong>的元素，把它交换到<strong>第一个</strong>位置
- 在剩下的（未排序的）部分中找出最小的，放到<strong>第二个</strong>位置
- … 以此类推

![w:1000](kepek/h05_kivalasztasos.svg)

---

<!-- _class: kicsi tomor -->

## 选择排序 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Procedure SelectionSort(A, n)
  For i ← 1 to n − 1
    min ← i
    For j ← i + 1 to n
      If A[j] < A[min] then
        min ← j
      End if
    End for
    swap(A[i], A[min])
  End for
End procedure
```

内层循环就是<strong>求最小值</strong>（第 2 周：求最大值）。

</div>
<div>

<span class="cimke java">Java</span>

```java
for (int i = 0; i < n - 1; i++) {
    int min = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[min]) min = j;
    int t = a[i];
    a[i] = a[min];
    a[min] = t;
}
```

<span class="cimke go">Go</span>

```go
for i := 0; i < len(a)-1; i++ {
    min := i
    for j := i + 1; j < len(a); j++ {
        if a[j] < a[min] {
            min = j
        }
    }
    a[i], a[min] = a[min], a[i]
}
```

</div>
</div>

---

## 选择排序 – 分析

| 情况 | 比较次数 | 交换次数 |
|---|---|---|
| 所有情况 | n(n − 1) / 2 | n − 1 |

- 步数：<strong>总是 O(n²)</strong> – 即使数组有序，也要扫描剩余部分
- 只有 <strong>n − 1 次交换</strong> – 移动代价很高时（大记录）很有用
- <strong>原地</strong>排序
- <strong>不稳定：</strong>远距离交换可能越过相等的元素
  `[5a, 5b, 2]` → `[2, 5b, 5a]`

---

<!-- _class: fejezet -->

# 插入排序

---

## 插入排序 – 思路

- 就像整理手中的扑克牌：把下一张牌<strong>插入</strong>到已经排好的牌中的正确位置
- 数组的前一部分是有序的；下一个元素向左移动，直到到达它的位置

![w:1000](kepek/h05_beszurasos.svg)

---

<!-- _class: kicsi tomor -->

## 插入排序 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Procedure InsertionSort(A, n)
  For i ← 2 to n
    x ← A[i]
    j ← i − 1
    While j ≥ 1 and A[j] > x
      A[j + 1] ← A[j]
      j ← j − 1
    End while
    A[j + 1] ← x
  End for
End procedure
```

它不交换而是<strong>移动</strong>：一步就是一次赋值。

</div>
<div>

<span class="cimke java">Java</span>

```java
for (int i = 1; i < n; i++) {
    int x = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = x;
}
```

<span class="cimke go">Go</span>

```go
for i := 1; i < len(a); i++ {
    x, j := a[i], i-1
    for j >= 0 && a[j] > x {
        a[j+1] = a[j]
        j--
    }
    a[j+1] = x
}
```

</div>
</div>

---

## 插入排序 – 分析

| 情况 | 比较次数 | 移动次数 |
|---|---|---|
| 最好（已经有序） | n − 1 | 2(n − 1) |
| 最坏（逆序） | n(n − 1) / 2 | ~ n² / 2 |
| 平均 | ~ n² / 4 | ~ n² / 4 |

- 步数：<strong>O(n²)</strong>，在有序或<strong>基本有序</strong>的数组上 <strong>O(n)</strong>
- <strong>原地</strong>排序，<strong>稳定</strong>（用 `A[j] > x`，不能用 `≥`!）
- <strong>在线算法：</strong>可以按元素到达的顺序边接收边排序
- 在小数组上（n < 20）最快 – 专业的排序实现（Java、Go 类库）对小区间就使用它

---

<!-- _class: fejezet -->

# 比较

---

## 实测结果（n = 1000）

比较次数 / 移动次数（`SortCompare` 程序）：

| | 随机 | 有序 | 逆序 |
|---|---|---|---|
| <strong>冒泡</strong> | 499 004 / 750 423 | <strong>999 / 0</strong> | 499 500 / 1 498 500 |
| <strong>选择</strong> | 499 500 / <strong>2 997</strong> | 499 500 / 2 997 | 499 500 / 2 997 |
| <strong>插入</strong> | <strong>251 585</strong> / 252 589 | <strong>999 / 1 998</strong> | 499 500 / 501 498 |

<div class="doboz tipp">

移动 = 赋值（一次交换是 3 次赋值）。注意：选择排序的步数总是<strong>相同</strong>的，插入排序在有序数据上是<strong>线性</strong>的。

</div>

---

## 稳定性

![w:1000](kepek/h05_stabilitas.svg)

- <strong>为什么重要？</strong>如果先按姓名排序，再用<strong>稳定</strong>排序按分数排序，分数相同的学生仍然保持字母顺序
- 稳定：冒泡、插入 · 不稳定：选择

---

## 应该选哪一种？

| | 冒泡 | 选择 | 插入 |
|---|---|---|---|
| 最坏情况 | O(n²) | O(n²) | O(n²) |
| 最好情况 | O(n) | O(n²) | O(n) |
| 交换 / 移动 | 多 | <strong>少（n − 1）</strong> | 中等 |
| 稳定 | 是 | 否 | 是 |
| 原地 | 是 | 是 | 是 |

- 一般情况：<strong>插入排序</strong> – 简单，在基本有序的数据上很快
- 移动代价高时：<strong>选择排序</strong>
- 冒泡排序：主要用于教学

<div class="doboz">

它们都不适合很大的 <em>n</em>:n = 10⁶ 时约需 10¹² 步。解决办法：<strong>归并排序</strong>和<strong>快速排序</strong>（第 13 周），O(n log n)。

</div>

---

## 内置排序

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int[] a = {5, 2, 8, 1};
Arrays.sort(a);   // 基本类型:双轴快速排序

String[] s = {"Wuhan", "Eger"};
Arrays.sort(s);   // 对象:TimSort(稳定)

list.sort(Comparator
    .comparing(Student::score));
```

</div>
<div>

<span class="cimke go">Go</span>

```go
a := []int{5, 2, 8, 1}
slices.Sort(a)     // pdqsort

sort.Strings(s)

slices.SortStableFunc(st,
    func(x, y Student) int {
        return x.Score - y.Score
    })
```

</div>
</div>

实际中我们使用类库的排序 – 但<strong>必须了解它的工作原理</strong>，以及它在什么情况下有多快。

---

## 小结

- <strong>冒泡：</strong>交换相邻元素，每一趟最大的元素到达末尾 · O(n²)，稳定
- <strong>选择：</strong>最小值放到前面 · 总是 O(n²)，只有 n − 1 次交换，不稳定
- <strong>插入：</strong>把下一个元素插入有序部分 · O(n²)，在有序数据上 O(n)，稳定
- 三者都是<strong>原地</strong>排序
- <strong>稳定性：</strong>键相等的元素保持原来的顺序

<strong>下周：</strong>集合数据结构 – 位向量、无序表示和有序表示、集合运算。

---

## 复习题

1. 在纸上用三种方法分别对数组 `[4, 1, 3, 2]` 排序！逐步写出各个状态！
2. 判断对错：选择排序在有序数组上只需 O(n) 步。
3. 哪种排序的交换次数最少？是多少？
4. 判断对错：冒泡排序是稳定的。
5. 对 10 个元素的逆序数组，插入排序进行多少次比较？
6. 如果插入排序用 `A[j] ≥ x` 代替 `A[j] > x`，会怎样？

<!--
答案：
1. 冒泡：[1,3,2,4] → [1,2,3,4] →（无交换）结束。
   选择：[1,4,3,2] → [1,2,3,4] → [1,2,3,4]。
   插入：[1,4,3,2] → [1,3,4,2] → [1,2,3,4]。
2. 错 – 总是 n(n−1)/2 次比较。  3. 选择排序，至多 n − 1 次。  4. 对
5. 10·9/2 = 45  6. 仍然能排好序，但不再稳定（而且会做多余的移动）。
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# 实践课

---

<!-- _class: gyak -->

## 示例程序

| 程序 | Java | Go | 演示内容 |
|---|---|---|---|
| 简单排序 | `SimpleSorts.java` | `w05/simplesorts` | 三种排序，逐步打印 |
| 比较 | `SortCompare.java` | `w05/sortcompare` | 不同输入下的比较次数、移动次数、时间 |

<div class="doboz tipp">

运行 `SortCompare` 程序！哪种排序依赖于输入，哪种不依赖？<em>n</em> 加倍时，运行时间怎样变化？

</div>

---

<!-- _class: gyak -->

## 练习

1. <strong>是否有序？</strong>用 O(n) 步判断数组是否按递增顺序排列！
2. <strong>降序：</strong>把插入排序改写成降序排序！
3. <strong>字符串：</strong>用选择排序对城市名数组排序！
4. <strong>记录：</strong>按分数对学生（姓名、分数）进行<strong>稳定</strong>排序！
5. <strong>最小的 k 个：</strong>用选择排序的前 <em>k</em> 步找出数组中最小的 <em>k</em> 个元素！需要多少步？
6. <strong>计数排序：</strong>不用比较，用 6 个元素的计数数组对考试成绩（1–5）排序！需要多少步？
7. <strong>逆序对：</strong>统计数组中顺序错误的元素对！它和冒泡排序有什么关系？

参考答案：`Exercises05.java`、`w05/exercises`

---

<!-- _class: gyak -->

## 课后作业

1. <strong>鸡尾酒排序：</strong>冒泡排序的一种变体，交替地从左往右和从右往左遍历。实现它，并测量在数组 `[2, 3, 4, 5, 1]` 上能节省多少次比较！
2. <strong>二分插入排序：</strong>用二分查找（第 2 周）确定插入位置！比较次数和移动次数怎样变化？
3. 举一个例子证明选择排序<strong>不稳定</strong>！
4. 把学生<strong>首先按分数</strong>降序排列，<strong>分数相同时按姓名</strong>排列！（提示：先后进行两次稳定排序，或者使用组合比较。）

<!--
解题思路：
1. 冒泡：需要 4 趟（1 每一趟只向左移动一个位置）；鸡尾酒：一次往返之后就有序了。
2. 比较次数降为 O(n log n)，移动次数仍为 O(n²) → 总体仍是 O(n²)。
3. [2a, 2b, 1] → 第一步 2a ↔ 1 → [1, 2b, 2a]。
4. 先按姓名，再按分数稳定排序；或者比较时：分数不同 → 按分数，否则按姓名。
-->