如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。
- 稳定的排序算法：插入排序、归并排序
- 不稳定的排序算法：选择排序、希尔排序、快速排序和堆排序
一般只有在稳定性是必要的情况下，稳定的排序算法才有优势。
| 算法 | 是否稳定 | 是否为原地排序 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 选择排序 | 否 | 是 | N^2 | 1 | |
| 插入排序 | 是 | 是 | 介于 N 和 N^2 之间 | 1 | 取决于输入元素的排列情况 |
| 希尔排序 | 否 | 是 | NlogN? | 1 | |
| 快速排序 | 否 | 是 | NlogN | lgN | 运行效率由概率提供保证 |
| 三向快速排序 | 否 | 是 | 介于 N 和 NlogN 之间 | lgN | 运行效率由概率保证，同时也取决于输入元素的分布情况 |
| 归并排序 | 是 | 否 | NlogN | N | |
| 堆排序 | 否 | 是 | NlogN | 1 |
快速排序是最快的通用排序算法。
Java 的系统程序员选择对原始数据类型使用（三向切分的）快速排序，对引用类型使用归并排序。暗示着用速度和空间（对于原始数据类型）来换取稳定性（对于引用类型）。
-
商业计算。
政府组织，金融机构和商业企业通过对其进行分类来组织大部分信息。信息是按名称或数字排序的帐户，按时间或地点排序的交易，按邮政编码或地址排序的邮件，按名称或日期排序的文件，或者其他任何处理此类数据的信息肯定是在整个过程中的某个地方涉及排序算法。
-
搜索信息。
按排序顺序保存数据可以使用经典二进制搜索算法有效地搜索数据。
-
行动调查。
假设我们要完成N个作业，其中作业j需要t j 秒的处理时间。我们需要完成所有工作，但希望通过最小化工的平均完成时间来最大化客户满意度。该处理时间最短第一规则，我们在增加了加工时间顺序安排工作，被称为实现这一目标。另一个例子，考虑 负载平衡问题，我们有完成M个相同的处理器和N个作业，我们的目标是安排处理器上的所有作业，以便尽可能早地完成上一个作业的时间。这个具体问题是NP难的（见第6章），所以我们不希望找到一种实用的方法来计算最佳时间表。已知产生良好调度的一种方法是 最长处理时间第一规则，其中我们以处理时间的递减顺序考虑作业，将每个作业分配给首先变得可用的处理器。
-
事件驱动的模拟。
许多科学应用涉及模拟，其中计算的重点是模拟现实世界的某些方面，以便能够更好地理解它。有效地进行这样的模拟可能需要适当的算法和数据结构。我们考虑6.1节中的粒子碰撞模拟 来说明这一点。
-
数值计算。
科学计算往往关注准确性（我们与真正的答案有多接近？）。当我们使用估计值执行数百万次计算时，准确性非常重要，例如我们通常在计算机上使用的实数的浮点表示。一些数值算法使用优先级队列和排序来控制计算的准确性。
-
组合搜索。
人工智能的一个典型范例是定义一组配置，这些配置具有从一个配置到下一个配置的明确定义的移动以及与每个移动相关联的优先级。还定义了一个启动配置和一个目标 配置（对应于解决了问题.A *算法 是一个解决问题的过程，我们将启动配置放在优先级队列上，然后执行以下操作直到达到目标：删除优先级最高的配置并将所有可以通过一次移动（不包括刚移除的移动）的配置添加到队列中。
-
Prim算法和Dijkstra算法是处理图形的经典算法。优先级队列在组织图搜索方面发挥着重要作用，可实现高效的算法。
-
Kruskal的算法 是另一种经典的图形算法，其边缘的权重取决于按重量顺序处理边缘。它的运行时间主要是排序成本。
-
霍夫曼压缩 是一种经典的数据压缩算法，它依赖于通过组合两个最小权重来处理具有整数权重的一组项目，以产生一个新权重，其权重是其两个成分的总和。使用优先级队列立即实现此操作。
-
字符串处理 算法通常基于排序。例如，我们将讨论用于在一组字符串中找到最长公共前缀的算法，以及在给定字符串中基于对字符串进行第一次排序后缀的最长重复子字符串的算法。