排序算法简介
基本概念#
整理“表”中的记录，使之按关键字递增（或递减）有序排列。
例如输入：
$n$ 个记录 $[R_0,R_1,R_2,…R_{n-1}]$，
关键字为 $[K_1,K_2,K_3,…K_{n-1}]$
经过排序…
输出：
$[R_{i0},R_{i1},R_{i2},…R_{in-1}]$，
使得 $[k_{i0}<=k_{i1}<=k_{i2}<=…<=k_{in-1}]$
（或者 $[k_{i0}>=k_{i1}>=k_{i2}>=…>=k_{in-1}]$）
排序算法的性能评价#
分别通过 算法复杂度 和 算法稳定性 来评价排序算法的性能优劣。
算法稳定性
当待排序记录的关键字均不相同时，排序的结果是惟一的，也是稳定的。
如果待排序的表中，存在有多个关键字相同的记录：假如经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。