排序问题

概述

排序问题 是算法设计中最基本的问题之一：给定一个元素序列，将其按非递减顺序重新排列。排序问题是衡量算法设计技术优劣的经典基准问题。

定义

排序问题

输入：包含 $n$ 个数的一个序列 $⟨a_1,a_2,\dots ,a_n⟩$。 输出：输入序列的一个排列 $⟨a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }⟩$，使得 $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$。

核心性质

• 关键字（Key）：决定元素排序顺序的值。排序操作实际是对关键字的排序。
• 卫星数据（Satellite Data）：与关键字一起移动的附带信息。排序时关键字是排序依据，卫星数据跟随关键字一起移动。
• 原地排序：仅需常数额外空间的排序算法（如插入排序、堆排序）。
• 稳定性：相等关键字元素的相对顺序在排序后保持不变。

章节扩展

第2章：入门

• 2.1 插入排序：以排序问题为背景引入插入排序，讨论了关键字与卫星数据的概念。
• 2.3 分治法：以排序问题为背景引入归并排序，展示了分治策略如何将排序问题的复杂度从 $\Theta (n^2)$ 降低到 $\Theta (n\lg n)$。

参见

• 插入排序
• 归并排序
• 分治法