4.1　排序算法概述

排序（Sort）是将一组数据按照一定的规则来进行排列，一般按递增或递减的顺序来进行排列。排序算法是一种最基本的算法。排序虽然看似是一个简单的问题，但是在实际的应用场合往往面临一些困难。比如实际应用中的数据量往往非常庞大，因此算法的效率和排序的速度就是一个很大的问题。往往需要寻找一个高效的排序算法，因此便演变出了多种排序算法。

排序算法的分类，如图4-1所示。最基本的排序算法包括交换排序算法、选择排序算法、插入排序算法和合并排序算法。其中，交换排序主要包括冒泡排序算法和快速排序算法；选择排序主要包括选择排序算法和堆排序算法；插入排序主要包括插入排序算法和Shell排序算法。

图4-1　排序算法的分类

上述几种基本排序算法直接对计算机内存中的数据进行排序。而对于一些大的文件，由于计算机的内存有限，往往不能直接将其读入内存进行排序。这时可以采用多路归并排序法，将文件划分为几个能够读入内存的小部分，然后分别读入进行排序，经过多次处理即可完成大文件的排序。

每一种排序算法都有其各自的特点，往往在某些特定的场合具有比较好的执行效率。因此，读者需要根据实际问题的需要来合理选择排序算法。下面对排序算法进行详细的介绍。

在实际应用中，基本的排序对象是整数，而基本排序规则包括从小到大排序和从大到小排序。下面主要以整型数据从小到大进行排序为例来讲解。对于其他类型的数据，或者从大到小的排序方法均类似。