《Unity3D高级编程之进阶主程》第一章，C#要点技术(五) 排序算法

年纪越大写程序写的越多，时间越长就越觉得算法的重要性，基础能力决定你到底能走多远。我们不是写一两年程序就完事了，从毕业算起，我们可能要写20-30年的程序，这段漫长的长跑路程中，最终比的不是谁熟悉API比较多，也不是谁用插件用的有多熟练，更不是比谁更熟悉某软件，而是比谁的基础能力强，比谁的算法效率高，比谁对底层原理更加熟知于心，比谁能够解决更复杂的系统和需求。

===

这其中算法能力比较重要，在程序员生涯中算法能力是基础能力的一种，很多时候程序的好坏，一方面看的是写程序的经验，另一方面看的是对计算机原理的理解程度，还有一方面看的是对算法的理解和运用熟练度。

算法能力不仅仅代表的是表面的算法熟知度，也是一种追求卓越的精神高度，即对所有经过自己手的程序效率负责的精神高度。在平时工作中某一处的算法有可能运用的很好，其他地方却依然用了很烂的算法或者算法运用的不太妥当，其对于整体程序效率来说效率依然很糟糕。因此在平时的编程习惯中，做到时刻关注算法效率是区分中、高水平的一个大的关键点。

在平时的编程工作中，排序和搜索算法最为常用。毫不夸张的说一个项目中有90%的算法都是排序和搜索算法，如果说我们把这90%的算法提高到一个很高效的程度，那么剩下的10%算法处理起来压力会小很多。我们这节就来讲讲排序的各种算法，以及运用到具体项目中去时的优劣程度。

快速排序算法

快速排序，是种最坏情况为O(n^2)的排序算法，虽然这个最坏情况比较差但快速排序通常是用于排序的最佳的实用选择，这是因为它的平均性能比较好，其排序期望运行时间为 O(nlogn) 且 O(nlogn)记号中隐含的常数因子很小，另外还不消耗额外的内存空间，在嵌入式虚存环境中也能很好工作，因此广受人们欢迎是最常用最好用用的最多的排序算法。

快速排序算法的排序步骤很简单：

1.从序列中选一个元素作为基准元素

2.把所有比基准元素小的元素移到基准元素的左边，把基准元素大的移到右边。

3.对分开来的二个一大一小的区块进行递归再筛选，对两个区块同样进行1、2的两个步骤处理。

简单来说就是选取一个区域里的数字，把这个区域按这个数字分成两半，一半小一半大，然后继续对这两半做同样的操作，直到所有筛选都完成就完成了排序。

排序算法最差的情况是，每次都选到一个最小的或最大的数字，这样每次筛选大小时都要充分移动，这种概率比较低。快速排序是最常用的排序方法，所以我们要着重优化此算法，对大量使用的算法和程序我们需要格外的重视。

优化：

1.随机选择中轴数

在快速排序中为了选择哪个元素作为中位数是比较关键的，这影响了算法排序效率，如果选中的数字不是中间的数字，而是一个比较偏小或者比较偏大的数字，那么排序的速度就会大大降低。如果选中的刚好是最大的或者最小的数字则更加糟糕，左边或右边完全没有数字可以排，相当于一次完整的遍历只排序了一个元素。

如果我们去找到区间的那个准确的中位数会增加更多消耗，所以我们只能减少得到最坏情况的概率，我们可以随机一个列表上的元素来作为基准元素，随机是为了减小选到最大和最小值的概率，但随机也时常会选到坏的基准元素，实际上随机数并没有对排序提供多大的帮助。

2.三数取中

为了让选择的中轴数更加接近中位数，可以先选择头、中点、尾，三个数字先来次排序，把最小的放在头，中间的放在中，最大的放在尾，用三个数字去提高有效接近中位数的中轴元素。

每次每个区间的头、中、尾的排序前都做这个操作，也就是说每次排序前，中轴数数都不可能是最小的，起码是区间里第2小的或者第2大的，这样选出来的中轴数靠近中位数的概率就很大了。

那么是否可以把三个数扩大到4个或M个数，其实过多数字的选择就相当于多出了个一个排序算法，减慢的二分排序的效果，实际效果不如3个数字来的快。虽然可以用随机选取3个数字的方式来替代做选择，但实际上随机选择并没有什么帮助，况且伪随机数的计算和冲突的解决也是需要消耗cpu的，因此最终还是使用三数取中的做法是选择接近中位数的比较有效的办法。

3，小区间使用插入排序

排序算法都有各自的使用量级，当量级不同时则排序效率可能不一样，插入排序就依赖于序列的有序性和排序元素数量，即排序的效率由排序列表的有序程度决定，也与排序的元素数量多少有关，如果序列的排序刚好是反序的则排序时效率最差，反之如果是有序序列则效率最快。

插入排序有一个特点，排序序列越长效率越差，对于短序列的排序效果则很好，高效排序序列长度在8左右。于是我们可以用这个特点来改善我们在快速排序中的效率，即在排序中，当切分的区块小于等于8个时，就采用插入排序来替代快速排序，因为8个以下的元素排序时，插入排序能发挥出更好的效率，我们就混合它与快速排序的逻辑关系，这样使得排序效率更高，其他时候任然采用快速排序算法。

4，缩小分割范围，与中轴数相同的合并在一起

除了选择更加靠近中位数的数字作为中轴数，以及小范围时使用更快的排序方式外，我们还可以通过缩小排序范围来提高排序效率。

我们可以把与中轴数相同的数可以合并到中轴数左右的位置，这样使得分割后的两边范围缩小，范围越小排序的速度就越快，刨去了更多不需要排序的元素。具体操作步骤为，每次在分割比较中，当元素与中轴数相等时则直接移动到中轴数身边，移动完毕后划分范围从中轴数变为最边上的相同元素的位置，用这种方式来缩小范围，让后续的排序减少排序元素。

快速排序是最常用也是使用范围最广的排序算法，铭记于心是有必要的。

除了快速排序，堆排序也是相对比较常用的，特别是堆排序的优先级队列

堆排序本身结构是由完全二叉树这样的结构支撑的，普通的堆排序比快速排序更低效一点，但堆排序中的最大最小堆的优先级队列异常用有，即只关注最大或最小值，在不断增加和删除根节点元素的情况下获取最大或最小值。优先级队列在排序完成后，数据堆就成了一个头顶着一个最大值或最小值的数据结构，这种数据结构更有利于获取根节点的最大最小值节点，在后面程序逻辑中当需要插入新元素、修改旧元素、以及推出最大最小值时效率比较高。优先级队列在实时获取最大最小值时高效的特点，导致它在寻路系统的A星算法中特别有用，因此最大最小堆排序常常用于A星算法。

由于堆排序是一种完全二叉树结构，所以这种结构可以用一维数组表示，这样则会让效率更加高一些因为内存是连续的。一维数组在表示二叉树时，通常都是以完全二叉树形式表示每个节点与其子节点，每个节点都一一对应数组上的索引规则，即如果 i 为节点索引时，则i2 和 i2+1 就是它的两个子节点，而索引 i 的父节点位置可以用 i/2 来表示，数组中任何节点都以遵循这种规则。以此类推到子节点，即 (i2)2 和 (i2)2+1 就是 i2 这个索引的两个字节点，所有子节点自身的索引直接除以2就是父节点的索引，即 i2 和 i*2+1 的除以2后取整就是他们的父节点索引 i 。

最大最小堆的优先级队列的操作分为，插入元素，返回最大或最小值，返回并删除最大最小值，查找并修改某个元素，其中关键的算法在于插入新元素和删除最大最小元素。其基本思想是利用完全二叉树的特性将新元素放入二叉树的叶子节点上，然后比较它与父节点的大小，如果它比父节点大(最小堆的情况)则结束，否则就与父节点交换一下，继续比较直到没有父节点或者父节点比它小。删除根节点则反过来，把叶子节点放入根节点，然后找到这个新根节点的实际位置，即比较它与两个子节点大小，如果比它们小(最小堆的情况)则结束，否则取最小值(最小堆的情况)替换节点位置，然后再继续向下比较和替换，直到停止或者替换到叶子节点时再没有子节点可比较就算完成操作。

我们来看两幅图就能很好的理解插入与删除的步骤：

缺图1

缺图2

图1为插入时的堆排序步骤，不断与父节点比较并交换，直到到根节点或者无法交换。图2为删除根节点的情况，把根节点与叶子节点交换后，叶子节点再从根部不断比较并下移到应有的位置。

其他排序算法简要概括

其他排序虽然使用频率没有快速排序来的多，但也会在很多特定的系统上出现。

桶排序，把所有的元素按一定大小范围分成N个组，对每个组进行快速排序，最终得到有序的数组，并且得到N个桶的记录，虽然第一次排序的速度不怎么样，但这N个桶的信息记录下来后对于后面的程序逻辑有非常大的帮助。比如我们需要进行模糊排序或模糊搜索，这种桶信息就会有很大帮助。

基数排序，是针对元素的特性来实时的‘分配式排序’，利用数字的特性按个位数，十位数，百位数的性质放入0-9的桶中不用排序，几次合并后就有了序数组，利用元素特性排序的速度比任何其他排序方式都要快速。这种算法思路教会我们在运用算法时，可以从元素的特性着手，找到它的特点就有可能找到更合适更快的算法。

基本的、常用的几种排序算法是我们必须了解的，面对比较复杂难解决的难题，我们就需要更为广阔的思路，算法在实际运用中并不是固定的，适合的才是最好的，我们应该随着问题环境的变化而变化，找到最佳的突破口。