排序（sorting）

什么是排序

将一组杂乱无章的数据按一定规律顺次排列起来。

• 数据表 (datalist)：它是待排序数据对象的有限集合。
• 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。

排序的目的是什么？

便于查找！

什么叫内部排序？什么叫外部排序？

• 若待排序记录都在内存中，称为内部排序；
• 若待排序记录一部分在内存，一部分在外存，则称为外部排序。

外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

排序算法的好坏如何衡量？

• 时间效率——排序速度（比较次数与移动次数）
• 空间效率——占内存辅助空间的大小
• 稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

排序的分类

内部排序

• 插入排序
• 交换排序
• 选择排序
• 归并排序
• 基数排序

外部排序

• 借助外部的辅助存储器（比如：硬盘），由于数据是存在外存中，故数据不可随机被存取

存储方式

• 地址连续的一组存储单元（记录之间的次序关系由存储位置决定，实现排序必须借助移动记录）
• 静态链表（记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针）－－链表排序
• 地址连续的一组存储单元，另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中的地址，在排序之后再按照地址向量中的值调整记录的存储位置－－地址排序

#define MAXSIZE 20  // 设记录不超过20个
typedef int KeyType;  // 设关键字为整型量（int型）typedef struct {// 定义每个记录（数据元素）的结构KeyType key;  // 关键字InfoType otherinfo;  // 其他数据项
} RedType;typedef struct {// 定义顺序表的结构RedType r[MAXSIZE + 1];  // 存储顺序表的向量// r[0]一般作哨兵或缓冲区int length;  // 顺序表的长度
} SqList;

各种排序算法比较

（数据不是顺次后移时将导致方法不稳定）

---

排序算法比较

• 按平均时间排序方法分为四类

  • O(n^2)
  • O(nlogn)
  • O(n^(1+r))
  • O(n)

• 快速排序是基于比较的内部排序中平均性能最好的

• 基数排序时间复杂度最低，但对关键字结构有要求

• 为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构

  • 直接插入排序
  • 归并排序
  • 基数排序

• 不宜采用链表作为存储结构的

  • 折半插入排序
  • 希尔排序
  • 快速排序
  • 堆排序

排序算法选择规则

• n较大时
  • 分布随机，稳定性不做要求，则采用快速排序
  • 内存允许，要求排序稳定时，则采用归并排序
  • 可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序
• n较小时
  • 基本有序，则采用直接插入排序
  • 分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序