定义

排序，又称为「分类」，是按照关键字的升序或降序，将一组数据进行重新排列的过程。

注意「关键字」这三个字，不能想当然的认为排序是对元数据（数字、字符串等）进行的操作。

分类

根据不同的标准，有以下分类成对出现：

  • 外排序 和 內排序
    • 对外存储介质（通常是硬盘）有无需求
    • 我们一般接触到的都属于内排序 即只在内存中进行排序
  • 不稳定排序 和 稳定排序
    • 排序后，相同关键字值的记录的相对先后顺序是否变化
  • 连续数据结构（一般为数组）排序和链表数据排序
    • 对被排序的数据结构而言

基本运算

查找（主要） + 移动，因而对算法的分析也主要体现在这两者上面。

常用的算法

  • 插入排序 insertion sort
  • 冒泡排序 bubble sort
  • 选择排序 selection sort
  • 谢尔排序 shell sort
  • 快速排序 quick sort
  • 堆积排序 heap sort
  • 归并排序 merge sort