排序算法

• 排序算法(Sort Algorithm)是将一组数据，依指定的顺序进行排列的过程。

排序的分类：

• 内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。

  • 插入排序：直接插入排序、希尔排序
  • 选择排序：简单选择排序、堆排序
  • 交换排序：冒泡排序、快速排序
  • 归并排序
  • 基数排序

• 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

• 内排序：所有排序操作都在内存中完成；

• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

• n: 数据规模

• k: “桶”的个数

• In-place: 不占用额外内存

• Out-place: 占用额外内存