排序算法作为算法中比较常见的类型，我们在写代码时经常会遇到和使用。
此篇博客主要介绍了排序算法涉及的一些概念和常见的排序算法。
稳定性
在排序算法中，在存在多个相同值项的情况下，如果在经过排序后，这些项的相对次序保持不变，则称这种排序算法是稳定的。否则称为不稳定的。
即如果 a = b , a 在 b 之前，如果在排序后，a 仍在 b 之前，则排序算法是稳定的。如果排序后，a 与 b 交换了位置，则称排序算法是不稳定的。
排序算法是否为稳定的是由算法的具体实现决定的。例如冒泡算法中，如果将比较条件修改为a[j] >= a[j+1]，则此时的冒泡算法就成为了不稳定的排序算法。
当然，在数据的顺序没有什么特殊意义时，考虑算法稳定性其实也没什么意义。
内排序和外排序
内排序：即所有排序操作都在内存中完成的排序算法。
外排序：在数据量比较大的情况下，将数据放在磁盘中。在排序时需要磁盘和内存的数据传输。
常见的排序算法
常见的排序算法共有十种，关于它们的相关信息如下表所示：
| 排序算法 | 平均时间复杂度 | 最好情况 | 最差情况 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | 不稳定 |
| 插入排序 | O(n²) | O(n) | O(n²) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 不稳定 |
| 希尔排序 | O(n log n) | O(n log²n) | O(n log²n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 基数排序 | O(n × k) | O(n × k) | O(n × k) | 稳定 |
其中时间复杂度中的 k ，代表的是 “ 桶 “的个数。
此篇博客仅对排序算法做了最基本的说明。每种排序算法的具体原理和详细的语言层面实现，将在后续算法学习相关博客中进行详细介绍。
同时在这里推荐两个可视化排序算法的网站，可以通过动画的形式，对各个排序算法有一个直观的了解。