排序算法在日常的应用

说到排序算法，它是计算机技术中最基本使用率最高的算法，需要非常复杂的算法都会用到排序，所以了解排序算法的思想和原理，对于编写软件非常重要。“工欲善其事必先利其器。”想要利用好排序算法，就必须对它有足够深刻的了解，才能在编写中用好。

从计算机算法角度来分析，衡量一个算法的优劣，主要通过时间复杂度、空间复杂度、稳定性和适用范围来考虑。

排序算法是非常常用的算法类别，比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍认为30%的计算周期都用在了排序上，今天这个比例可能降低了，大概是因为现在的排序算法更加高效。现在这个时代数据可以说是无处不在，而整理数据的第一步往往就是进行排序。所有的计算机系统都实现了各种排序算法以供系统和用户使用。   

（1）理解数据的特点

使用排序处理数据有利于理解数据的特点，方便我们之后的分析与视觉化。像一些生活中的例子比如词典，菜单，如果不是按照一定顺序排列的话，人们想要找到自己需要的东西的时间就会大大增加。

计算机需要处理大规模的数据，排序后，人们可以根据数据的特点和需求来设计计算机的后续处理流程。

（2）降低时间复杂度

使用排序预处理可以降低求解问题所需要的时间复杂度，通常是一个以空间换取时间的平衡。如果一个排序好的列表需要被多次分析的话，只需要耗费一次排序所需要的资源是很划算的，因为之后的每次分析都可以减少很多时间。

（3）稳定性方面

如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。这个性质在许多情况下很重要。例如：在考虑一个需要处理大量含有地理位置和时间戳的事件互联网商业应用程序。

首先，我们在时间发生时将它们挨个存储在一个数组中，这样在数组中它们已经是按照时间顺序排序好了的。现在假设在进一步处理前将按照地理位置划分。一种简单的方法是将数组按照位置排序。如果排序算法不是稳定的，排序后的每个城市的交易可能不会再是按照时间顺序排序的了。

很多情况下，不熟悉排序稳定性的程序员在第一次遇到这种情形的时候会在使用不稳定排序算法后把数组弄的一团糟而一脸懵逼。上一篇文章中我们讲到的插入排序和归并排序都属于稳定的，其他几个（选择，希尔，快速，堆排序）都是不稳定的。有很多办法能够将任意排序算法编程稳定的，但一般只有在稳定性是必要的情况下稳定的排序算法才有优势。不要想当然认为算法具有稳定性是理所当然的，但事实上没有任何实际应用中常见的算法不是用了大量额外的时间和空间才做到了这一点（研究人员开发了这样的算法，但应用程序员发现它们太复杂了，无法在实际开发中使用）。 

（4）排序应用

1. 商业计算

一般大量的信息都被存储在大型数据库中，能够按照多个键排序以提供搜索效率。

可以说没有线性对数级别的排序算法就没法将这些海量的数据进行排序，进一步处理这些数据也会变得极端困难，甚至是不可能的。

2. 信息搜索

有序的信息可以确保我们可以用经典的二分查找法来进行高效的搜索。

3. 运筹学

① 排序算法在调度中的应用

问题：假设我们需要完成N个任务，第j个任务需要耗时tj秒，我么需要在完成任务的同时，将每个任务的平均完成时间最小化。

思路：只要将任务按照处理时间升序排列就可以达到目标。

实现：因此按照最短优先原则，将任务按耗时排序，或者插入最小优先队列中，即可完成目标。

② 负载均衡问题

问题：假设我们有M个相同的处理器以及N个任务，目标是在尽可能短的时间内在这些处理器上完成所有任务。

思路：这个问题是NP-困难的，因此实际上不可能算出最优的方法，一种较优调度方法是最大优先。将任务按照耗时降序排列，将每个任务依次分配给当前可用的处理器。

实现：先逆序排序这些任务，然后为M个处理器维护一个优先队列，每个元素的优先级就是对应处理器上运行的任务耗时之和。每一步都删去优先级最低的处理器，将下个任务分配这个处理器，然后重新插入优先队列。

4. 值计算

一些数值计算算法采用优先队列和排序来控制计算中的精确度。

数值积分的一个方法，就是使用优先队列来存储一组小间隔中每段的近似精度。积分的过程就是删除精确度最低的间隔，并分为两段，然后将两段都重新加入优先队列，直到达到预期的精度。

5. 霍夫曼压缩

这是数据压缩中的一个经典算法。

算法处理的数据中每个元素都有一个小整数作为权重，处理的过程就是将权重最小的两个元素归并为一个新的元素，权重相加得到新元素的权重。

使用优先队列可以立即实现这个算法。

其他的几种数据压缩算法也是基于排序的。

6. 字符串处理

字符串算法常常依赖于排序算法（常用特殊的字符串排序算法）。