Skip to content

第 11 章:查找与排序初步 ​

本章能学到什么 ​

  • 顺序查找与二分查找的原理和写法
  • 冒泡排序与选择排序的完整过程
  • 用 C++ 自带的 sort 一行排好序
  • 「复杂度」这个概念的一句话印象

知识链位置:第 9、10 章讲了字符串和容器(数组、vector)。数据装进容器之后,最常见的两件事就是「找」和「排」。本章解决这两个问题。

从一个成绩单场景开始 ​

期末考试结束,全班 40 人的成绩存进了电脑:

cpp
vector<string> names  = {"小明", "小红", "小刚", /* …… */};
vector<int>    scores = {72, 85, 60, /* …… */};

班主任提出两个要求:

  1. 查一下小刚考了多少分——这是查找。
  2. 把全班按分数从高到低排队——这是排序。

这两件事在学校里天天发生。本章看看计算机怎么做,以及怎样做得更快。

顺序查找:一个一个看过去 ​

最朴素的办法:从第一个开始,逐个比较,找到就停。

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<string> names  = {"小明", "小红", "小刚", "小丽", "小华"};
    vector<int>    scores = {72, 85, 60, 95, 78};

    string target = "小刚";
    int found = -1;                       // -1 表示「还没找到」

    for (int i = 0; i < (int)names.size(); i++) {
        if (names[i] == target) {         // 逐个比较
            found = i;
            break;                        // 找到就停,不再往后看
        }
    }

    if (found != -1) {
        cout << target << "的成绩是" << scores[found] << endl;
    } else {
        cout << "没找到" << target << endl;
    }
    return 0;
}
text
小刚的成绩是60

这个方法和在作业本堆里翻自己的本子一样:运气好看一本就找到,运气差要翻完整堆。40 人最多看 40 次,4000 人最多看 4000 次。

二分查找:查字典的智慧 ​

查字典时没人从第一页开始翻。查「中」字,先翻到中间附近,发现是「王」部,知道「中」在前面,于是只翻前半本;再对半分,几次就到了。

这个办法叫二分查找。它有一个前提:数据必须已经排好序。乱序的字典没法这样查。

它和数学课上的「折半逼近」是同一招:每次排除一半,范围飞速缩小。

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> scores = {11, 12, 22, 25, 34, 64, 90};  // 前提:已从小到大排序
    int target = 25;

    int left = 0, right = (int)scores.size() - 1;  // 查找范围的两端
    int found = -1;

    while (left <= right) {
        int mid = (left + right) / 2;        // 取范围正中间
        if (scores[mid] == target) {         // 正好命中
            found = mid;
            break;
        } else if (scores[mid] < target) {
            left = mid + 1;                  // 目标在右半,砍掉左半
        } else {
            right = mid - 1;                 // 目标在左半,砍掉右半
        }
    }

    if (found != -1) {
        cout << "找到了,位置是" << found << endl;
    } else {
        cout << "没找到" << endl;
    }
    return 0;
}
text
找到了,位置是3

两种查找的差距有多大:

数据个数顺序查找最多看几次二分查找最多看几次
10104
1001007
1 0001 00010
1 000 0001 000 00020

一百万个数据,二分查找最多 20 次就能定位。因为每看一次,范围缩小一半,2 的 20 次方已经超过一百万。

上面的程序找 25 是一次命中。换成找 22,过程看得更清楚:

步数leftrightmidscores[mid]判断
10632522 更小,砍掉右半
20211222 更大,砍掉左半
322222命中

每一次比较,查找范围都缩小一半——这就是「折半」两个字的具体含义。

两种查找各适合什么场合:

场合该用哪种
数据没排序,也不想排序顺序查找
数据已排序,或要反复查很多次先排序,再二分查找
数据量很小(几十个)都行,顺序查找写起来更简单

冒泡排序:相邻的比大小,大的往后挪 ​

排序的数学基础就是「比大小」——数学课上比较两个数谁大,计算机反复做这件事就能把一队数排整齐。

冒泡排序的规则:从头到尾,相邻两个比大小,顺序不对就交换。一轮下来,最大的数像气泡一样「浮」到队尾。再来一轮,第二大的到位。如此反复。

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {64, 25, 12, 22, 11};
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {          // 共 n-1 轮
        for (int j = 0; j < n - 1 - i; j++) {  // 每轮比到「未排好」的末尾
            if (a[j] > a[j + 1]) {             // 前面比后面大
                int t = a[j];                  // 交换两个数
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i + 1 < n) cout << " ";
    }
    cout << endl;
    return 0;
}
text
11 12 22 25 64

每一轮结束后数组的样子(划线部分是已经排好的尾部):

轮次数组状态本轮归位的数
初始64 25 12 22 11—
第 1 轮后25 12 22 11 6464
第 2 轮后12 22 11 25 6425
第 3 轮后12 11 22 25 6422
第 4 轮后11 12 22 25 64全部

以第 1 轮为例,看「冒泡」是怎样发生的:

比较数组状态(加粗为正在比较的两个)是否交换
64 和 2564 25 12 22 11交换 → 25 64 12 22 11
64 和 1225 64 12 22 11交换 → 25 12 64 22 11
64 和 2225 12 64 22 11交换 → 25 12 22 64 11
64 和 1125 12 22 64 11交换 → 25 12 22 11 64

最大的 64 一路交换到队尾,像气泡浮上水面——「冒泡」这个名字就是这么来的。

一个常用的小优化:如果某一整轮下来一次交换都没发生,说明已经排好了,可以提前收工:

cpp
for (int i = 0; i < n - 1; i++) {
    bool swapped = false;                    // 本轮有没有交换过
    for (int j = 0; j < n - 1 - 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;                     // 一整轮没交换,提前结束
}

对几乎排好的数据,这个优化能省下大半时间。

选择排序:每轮挑出最小的放前面 ​

选择排序换了个思路:第一轮从全部数里找出最小的,和第 1 个位置交换;第二轮从剩下的里找最小的,和第 2 个位置交换。像体育老师排队:先挑出最矮的站排头,再从剩下的人里挑最矮的站第二个。

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {64, 25, 12, 22, 11};
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {
        int minPos = i;                        // 先假设第 i 个最小
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minPos]) {
                minPos = j;                    // 发现更小的,记下位置
            }
        }
        int t = a[i];                          // 最小的换到第 i 位
        a[i] = a[minPos];
        a[minPos] = t;
    }

    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i + 1 < n) cout << " ";
    }
    cout << endl;
    return 0;
}
text
11 12 22 25 64
轮次数组状态本轮动作
初始64 25 12 22 11—
第 1 轮后11 25 12 22 64最小的 11 换到最前
第 2 轮后11 12 25 22 64剩余中最小的 12 到位
第 3 轮后11 12 22 25 6422 到位
第 4 轮后11 12 22 25 6425 到位,结束

两种排序的比较:

对比点冒泡排序选择排序
每轮做什么相邻比较交换,最大数浮到尾部找出最小数,换到最前
交换次数多,逆序对都要交换少,每轮最多一次
好懂程度像气泡上浮像排队挑人

站在巨人肩上:库函数 sort ​

实际写程序时很少手写排序。C++ 标准库自带一个又快又可靠的 sort:

cpp
#include <iostream>
#include <vector>
#include <algorithm>          // sort 在这个头文件里
using namespace std;

int main() {
    vector<int> a = {64, 25, 12, 22, 11};

    sort(a.begin(), a.end());  // 从小到大,一行搞定

    for (int i = 0; i < (int)a.size(); i++) {
        cout << a[i];
        if (i + 1 < (int)a.size()) cout << " ";
    }
    cout << endl;
    return 0;
}
text
11 12 22 25 64

a.begin() 和 a.end() 表示「从开头到结尾」,意思是整个数组都参与排序。想从大到小排,可以排完再用 reverse(a.begin(), a.end()) 翻转。

手写冒泡和选择排序的意义不在于日常使用,在于理解「比较 + 交换」这套基本功。

给成绩单排序:两个数组一起动 ​

回到本章开头的成绩单。姓名和分数在两个数组里,按分数排序时,交换分数的同时必须交换对应的姓名,否则张冠李戴:

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<string> names  = {"小明", "小红", "小刚", "小丽"};
    vector<int>    scores = {72, 85, 60, 95};

    // 选择排序:按分数从高到低,姓名跟着一起动
    for (int i = 0; i < (int)scores.size() - 1; i++) {
        int maxPos = i;
        for (int j = i + 1; j < (int)scores.size(); j++) {
            if (scores[j] > scores[maxPos]) {
                maxPos = j;
            }
        }
        int t = scores[i]; scores[i] = scores[maxPos]; scores[maxPos] = t;
        string ts = names[i]; names[i] = names[maxPos]; names[maxPos] = ts;
    }

    for (int i = 0; i < (int)names.size(); i++) {
        cout << names[i] << " " << scores[i] << endl;
    }
    return 0;
}
text
小丽 95
小红 85
小明 72
小刚 60

这种「两个数组绑在一起动」的写法能工作,但很别扭,漏交换一个就出错。第 12 章会把姓名和分数装进一个包里,从根上消灭这种别扭。

为什么还要学手写排序 ​

既然 sort 一行就能排好,冒泡和选择为什么值得学:

理由说明
练基本功比较、交换、下标控制,是所有算法内容的共同起点
理解代价亲手写过,才知道排序不是「免费的」,数据大时要讲方法
应对变化按特殊规则排序(先按总分、同分再按学号)时,比较逻辑要自己写
考试与竞赛学校信息课、竞赛入门,这两个排序都是常驻题目

日常写程序用库函数,学习阶段写手写版——两件事不矛盾。

【跨语言对照】同一个冒泡,两种写法 ​

本质问题:冒泡排序的逻辑——比较、交换、轮数——在任何语言里都一样。不同的是写出来的样子。

写法差异C++Python
装数据的容器vector<int>列表 list
求长度a.size()len(a)
交换两个元素借助临时变量三行完成a[j], a[j+1] = a[j+1], a[j] 一行完成
输出一行数循环里逐个 cout" ".join(...) 拼接

C++ 版:

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {64, 25, 12, 22, 11};
    int n = a.size();

    cout << "排序前:";
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i + 1 < n) cout << " ";
    }
    cout << endl;

    for (int i = 0; i < n - 1; i++) {          // 冒泡排序
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    cout << "排序后:";
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i + 1 < n) cout << " ";
    }
    cout << endl;
    return 0;
}

Python 版(详见 《Python 从入门到精通》第 11 章):

python
a = [64, 25, 12, 22, 11]
n = len(a)

print("排序前:" + " ".join(str(x) for x in a))

for i in range(n - 1):                # 冒泡排序
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]   # 交换

print("排序后:" + " ".join(str(x) for x in a))

两段程序的输出完全一致:

text
排序前:64 25 12 22 11
排序后:11 12 22 25 64

为什么设计不一样:C++ 诞生于对性能和精确控制有要求的年代,交换也要程序员自己写清每一步,编译器才能生成高效的机器指令。Python 把「少打字」当作设计目标,交换这种高频操作直接做成语法。两种取向各有适用的场合,本章不做优劣评判。

一句关于「复杂度」的话 ​

计算机科学家用复杂度这个词描述「数据变多时,程序会变慢多少」。冒泡排序的数据量翻 10 倍,时间大约翻 100 倍;二分查找的数据量翻 10 倍,时间只增加一点点。这个概念现在只需有个印象,今后的学习中会反复遇到。

动手实验 ​

实验 1:把顺序查找程序里的 target 改成 "小王",运行程序,观察输出,解释为什么会这样。

💡 查看答案

输出 没找到小王。

循环把 5 个名字全部比较了一遍,没有任何一个等于 "小王",所以 found 始终是初始值 -1,程序走了 else 分支。这正是用 -1 做「没找到」标记的原因。

实验 2:修改冒泡排序程序,让数组从大到小排列,输出 90 64 34 25 22 12 11(先把数据换成 {11, 12, 22, 25, 34, 64, 90} 再改比较方向)。

💡 查看答案

只需把内层循环里的 > 改成 <:前一个数比后一个小就交换,大数就会逐渐浮到前面。

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {11, 12, 22, 25, 34, 64, 90};
    int n = a.size();

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] < a[j + 1]) {     // 只改这一行:小于就交换
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i + 1 < n) cout << " ";
    }
    cout << endl;
    return 0;
}
text
90 64 34 25 22 12 11

实验 3:数据 {90, 34, 11, 64, 25, 22, 12} 是乱序的。先用库函数 sort 把它排好,再用本章的二分查找代码找 64 的位置,输出 找到了,位置是5。

💡 查看答案
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {90, 34, 11, 64, 25, 22, 12};
    sort(a.begin(), a.end());          // 先排序:11 12 22 25 34 64 90

    int target = 64;
    int left = 0, right = (int)a.size() - 1;
    int found = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] == target) {
            found = mid;
            break;
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    if (found != -1) {
        cout << "找到了,位置是" << found << endl;
    } else {
        cout << "没找到" << endl;
    }
    return 0;
}
text
找到了,位置是5

排序后数组是 11 12 22 25 34 64 90,64 在第 5 个位置(从 0 开始数)。二分查找的前提「已排序」由 sort 保证,两个工具就这样配合起来了。