第 11 章アルゴリズムとデータ構造

並べる・探す・しまう。この章では次の 16 個の知識点を、解説・インタラクティブ教材・練習問題で学びます。

第 11 章算法与数据结构：排序、查找、存放

アルゴリズムと流れ図・基本 3 構造

アルゴリズムは問題を解く手順、プログラムはそれをコンピュータ向けの言語で書いたもの。手順は流れ図で表し、どんなアルゴリズムも 順次・選択・繰返し の 3 つの組合せで書ける。流れ図の問題は、変数の値を表にして追う（トレース）のが基本。

算法、流程图与三种基本结构：算法是解决问题的步骤，程序是把它用计算机能懂的语言写出来。步骤用流程图表示，任何算法都能用 顺序、选择、循环 三种结构组合而成。流程图题的基本解法是把变量值列成表逐步追踪。

配列（1 次元・2 次元と添字）

配列は同じ型のデータを入れる箱を並べたもの。各箱は添字（要素番号）で指定する：1 次元は List[4]、2 次元は List2[行, 列]。添字が 0 から始まるか 1 から始まるかは問題文の指定に従う（科目 B の擬似言語は 1 から）。

数组（一维、二维与下标）：数组是把存放同类型数据的格子排成一排。每个格子用下标指定：一维 List[4]，二维 List2[行, 列]。下标从 0 还是从 1 开始，按题目规定（科目 B 的伪代码从 1 开始）。

リスト（ポインタ・単方向 / 双方向）

リストは、各データに「次のデータの場所（ポインタ）」を持たせて数珠つなぎにしたデータ構造。挿入・削除はポインタを付け替えるだけで、他のデータを移動しなくてよい。双方向リストは「次」と「前」の 2 つのポインタを持つ。

链表（指针、单向 / 双向）：链表让每个数据都带着「下一个数据的位置（指针）」，像串珠一样连起来。插入、删除时只改指针，不用移动其他数据。双向链表有「后继」和「前驱」两个指针。

キューとスタック

キューは先に入れたものから出す（FIFO：待ち行列）、スタックは後に入れたものから出す（LIFO：積み重ね）。スタックに入れる操作を PUSH、取り出す操作を POP という。

队列与栈：队列是先放进去的先出来（FIFO，排队），栈是后放进去的先出来（LIFO，叠盘子）。入栈叫 PUSH，出栈叫 POP。

木構造（2 分木・2 分探索木・ヒープ）

木構造は階層でデータを持つ。一番上が根、子をもたない節が葉。2分探索木は 左の子＜親＜右の子、ヒープは 親 ≧ 子（または親 ≦ 子） が常に成り立つ 2 分木。ヒープは配列で表すと [i] の子が [2i]・[2i+1]。

树结构（二叉树、二叉搜索树、堆）：树结构用层级保存数据。最上面是根，没有子节点的是叶。二叉搜索树满足 左子 < 父 < 右子，堆满足 父 ≥ 子（或父 ≤ 子）。用数组表示堆时，[i] 的子节点是 [2i]、[2i+1]。

線形探索法（番兵を含む）

線形探索法は先頭から 1 つずつ順に比べて探す方法。データが整列されていなくても使えるが、比較回数は平均で約 n/2、最大 n 回（O(n)）。番兵を末尾に置くと「配列の終わりか」の判定を省ける。

线性查找（含哨兵）：线性查找从头开始逐个比较。数据不必排序，但比较次数平均约 n/2、最多 n 次（O(n)）。在末尾放一个哨兵，就能省去「是否到末尾」的判断。

2 分探索法

2分探索法は、整列済みのデータの真ん中と比べ、目的のデータがある側の半分だけを残すことを繰り返す探索法。比較のたびに候補が半分になるので、最大比較回数は約 $\log_2 n$ （⌊log₂n⌋ + 1 回）。

二分查找：二分查找对已排序数据，与中间元素比较，只保留目标所在的一半，反复进行。每比较一次候选减半，最多比较约 log₂n 次（⌊log₂n⌋+1）。

ハッシュ探索法（ハッシュ関数・シノニム）

ハッシュ探索法は、データからハッシュ関数で格納位置を計算し、その位置を直接見に行く方法。データ数に関係なくほぼ 1 回で見つかる（O(1)）。異なるデータが同じ位置になることを衝突（コリジョン）といい、そのデータをシノニムという。

散列查找（散列函数、同义词）：散列查找用散列函数从数据算出存放位置，直接去该位置找。与数据量无关，几乎 1 次就能找到（O(1)）。不同数据算出同一位置叫冲突，这些数据叫同义词。

基本交換法（バブルソート）

基本交換法は隣り合う 2 つを比べ、順序が逆なら交換することを繰り返す整列法。1 周するごとに端に 1 つ値が確定する（泡が浮かぶように移動するのでバブルソート）。計算量は O(n²)。

冒泡排序：冒泡排序反复比较相邻两个元素，顺序反了就交换。每一轮在一端确定一个值。复杂度 O(n²)。

基本選択法（選択ソート）

基本選択法は、未整列部分から最大（最小）値を選び、未整列部分の先頭と交換することを繰り返す整列法。1 周ごとに先頭側に 1 つ確定する。比較回数は n(n−1)/2 で O(n²)、交換は 1 周に 1 回だけ。

选择排序：选择排序反复从未排序部分选出最大（最小）值，与未排序部分的开头交换。每轮在前端确定一个。比较 n(n−1)/2 次，O(n²)，每轮只交换 1 次。

基本挿入法（挿入ソート）

基本挿入法は、整列済みの部分に、次のデータを正しい位置へ挿入することを繰り返す整列法。最悪 O(n²) だが、データがほぼ整列済みなら非常に速い（ずらす回数が少ない）。

插入排序：插入排序反复把下一个数据插入已排序部分的正确位置。最坏 O(n²)，但数据接近有序时非常快（移动次数少）。

シェルソート

シェルソートは、一定の間隔ごとに取り出したグループ内で並べ替え、間隔を狭めて 1 になるまで繰り返す整列法。最初に大まかに整えておくので、最後の間隔 1（普通の挿入法）が速く終わる。基本挿入法の改良版。

希尔排序：希尔排序按一定间隔分组、在组内排序，逐步缩小间隔直到 1。先大致排好，最后间隔 1（普通插入排序）就很快。是插入排序的改进版。

クイックソート

クイックソートは、基準値（ピボット）を選び、それより小さいグループと大きいグループに分けることを、グループが 1 個になるまで繰り返す（再帰）整列法。平均 O(n log n) で実用上とても速い。

快速排序：快速排序选一个基准值，把数据分成比它小和比它大的两组，对各组重复直到只剩 1 个（递归）。平均 O(n log n)，实际使用中非常快。

ヒープソート

ヒープソートは、データをヒープ（親 ≧ 子の 2 分木）にして根（最大値）を取り出し、一番下の葉を根に移してヒープを作り直すことを繰り返す整列法。O(n log n)。配列では [i] の子が [2i]・[2i+1]。

堆排序：堆排序把数据建成堆（父 ≥ 子），取出根（最大值），把最后一个叶子移到根，再重建堆，反复进行。O(n log n)。数组中 [i] 的子节点是 [2i]、[2i+1]。

マージソート

マージソートは、データが 1 個になるまで半分に分割し、整列しながら併合（マージ）して元に戻す整列法。併合は「2 つの列の先頭どうしを比べ、小さい（大きい）方から取る」だけ。O(n log n)。

归并排序：归并排序把数据对半分到每组 1 个，再边排序边合并。合并时只需「比较两列开头、取较小（大）者」。O(n log n)。

計算量とオーダー記法

計算量は、データ量 n が増えたときに処理回数がどう増えるかを表す。オーダー記法では最も増え方の大きい項だけを残す（ $n^2 + n + 10 \to O(n^2)$ ）。探索：線形 O(n)・2 分 O(log n)・ハッシュ O(1)。整列：基本 3 手法 O(n²)・クイック / ヒープ / マージ O(n log n)。

计算量与大 O 表示法：计算量表示数据量 n 增加时处理次数如何增长。大 O 表示法只保留增长最快的项（n²+n+10 → O(n²)）。查找：线性 O(n)、二分 O(log n)、散列 O(1)；排序：三种基本方法 O(n²)，快速/堆/归并 O(n log n)。

基本情報道場で学習を始める →

← 第 10 章情報セキュリティ　第 12 章プログラミングとオブジェクト指向 →

第 11 章 アルゴリズムとデータ構造