基础篇（六）——排序
假设含有n个记录的序列为{r1,r2,......rn}，其相应的关键字分别为{k1,k2,......kn}，需确定1,2......n的一种排列p1,p2......pn，使其相应的关键字满足kp1<=kp2<=......kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2......rpn}，这样的操作就称为排序。
一、排序的基本概念与分类
排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。
1.1排序的稳定性
假设ki=kj（1<=i<=n,1<=j<=n,i不等于j），且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列rj领先ri，则称所用的排序方法是不稳定的。
1.2内排序与外排序
内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。这里主要介绍内排序。
二、冒泡排序
冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
算法示例：
冒泡算法由双层循环实现，其中外层循环用于控制排序轮数，一般为要排序的数组长度减1次，因为最后一次排序只剩下一个数组元素，不需要对比，同时数组已经完成排序了。而内层循环主要用于对比数组中每个临近元素的大小，以确定是否交换位置，对比和交换次数随排序轮数减少。例如，一个拥有6个元素的数组，在排序过程中每一次循环的排序过程和结果如下图所示：
三、简单选择排序
简单选择排序法就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。
算法示例：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序的放在已排好序的数列的最后，直到全部待排序的数据元素排完。排序过程和结果如下图所示：
四、直接插入排序
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
小结：
直接插入排序的时间复杂度和冒泡排序与简单选择排序的时间复杂度一样。同样的时间复杂度，直接插入排序比冒泡和简单选择排序的性能要好一些。
五、希尔排序（对直接插入排序的改进）
直接插入排序，它的效率某些时候是很高的，比如，记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。但是这两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像{2,1,3,6,4,7,5,8,9}这样可以称为基本有序了。
跳跃分割策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
六、堆排序（对简单选择排序的改进）
堆排列就是对简单选择排序进行的一种改进。堆是具有下列性质的二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（左图）；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（右图）。
堆排序就是利用堆进行排序的方法。它的基本思路是，将待排序的的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，就能得到一个有序序列了。
堆排序小结：
堆排序的运行时间主要是耗费在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的交换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O（n）。
由于堆排序对原始记录的排序记录并不敏感，因此它无论是最好、最坏和平均时间复杂度是一样的。这在性能上要远远好于冒泡、简单选择、直接插入的时间复杂度。空间复杂度上，它只有一个用来交换的暂存单元，也很不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。
七、归并排序
将本是无序的数组序列{16,7,13,10,9,15,3,2,5，8,12，1,11,4,6,14}，通过两两合并排序后再合并，最终获得一个有序的数组。
归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并得到[n/2]个长度为2或1的有序子序列；再两两归并，......，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。
归并排序小结：
归并排序需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。归并排序是一种比较占用内存，但却效率高且稳定的算法。
八、快速排序（对冒泡排序的改进）
快速排序其实就是前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。
快速排序的基本思想：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序小结：
快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。在最优情况下，快速排序算法的时间复杂度为O(nlogn)。就空间复杂度来说，最好情况，递归树的深度为log2n，其空间复杂度就为O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为O（n），平均情况，空间复杂度也为O(logn)。
由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
九、总结
根据排序过程中借助的主要操作，将内排序分为：插入排序、交换排序、选择排序和归并排序四类。
将7种算法的各种指标进行对比：
从算法的简单性来看，将7种算法分为2类：
简单算法：冒泡、简单选择、直接插入。
改进算法：希尔、堆、归并、快速。
就平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3中简单算法。
从最好情况看，反而冒泡和直接插入更胜一筹，也就是说，如果待排序序列总是基本有序，反而不应该考虑4种复杂的改进算法。
从最坏情况看，堆排序与归并排序又强过快速排序以及其它简单排序。
从待排序的记录个数上来说，待排序的个数n越小，采用简单排序方法越合适。反之，n越大，采用改进排序方法越合适。
