对于排序而言，在生活中经常会遇到，比如学校考试成绩的排序，而对于排序也存在着其稳定性，像当学校有两个同学a和b的成绩相同的时候，我们通过学号()进行排序，在学号前面的a同学就会被排到第一，这种情况我们称为稳定排序，反之如果学号在前面的a同学并没有排到第一，而是b同学排到第一，那么我们称为不稳定排序。
对于排序而言我们还分为了两种形式：
- 内排序：在排序整个过程中，待排序的所有记录全部被放置在内存中
- 外排序：由于排序记录个数多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据
这里就主要了解内排序的算法性能：
- 时间性能
- 辅助空间
- 算法的复杂度
排序算法有许多，这里我们就介绍一些常见的吧。
先提供一个用于排序用的顺序表结构，此结构也将用于后面要讲的所有排序算法，这里我们从小标为1的索引开始，留下下标为0的索引作哨兵或者临时变量。
还有一个排序常用于数据交换的函数
冒泡排序(Bubble Sort)一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。
用标记变量flag来记录数据是否还需要进行两两交换，如果为FALSE则此序列已经有序了。
冒泡排序的时间复杂度为O(n²)
简单选择排序法(Simple Selection Sort)就是通过n-i此关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换。
选择排序的时间复杂度为O(n²)
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表，类似于当前面索引数据大于后面一位的时候，则会进行排序操作，前面会设置哨兵()，并且会将后面一位的值依次向前查找大于哨兵则后移一位，直到数据小于为止，之后再将哨兵()插入回正确的位置。
直接插入排序的时间复杂度在最好的情况下为O(n)，最坏的情况为O(n²),所以在性能上比冒泡和简单选择排序要好一些。
对于上面各种排序算法的时间复杂度基本上都是O(n²)，当很多人都以为这是极限的时候，突然出现了一个科学家改变了思维的方式，通过换位思考计算出了比O(n²)小的算法，而那位科学家就是希尔。
而他的算法思想其实为，将一个数组分成了三组，分别为上、中、下三部分组成，从小到大排序，最后在将这3组数据拼合起来就完成了排序方法，但是对于无序的数据而言，怎么能断定相邻的3个数据就一定在同一个部分当中呢?那么希尔排序的演变过程就诞生了，其通过一个增量的形式来记录两个值的间距，直到增量<=1为止完毕。
希尔排序的时间复杂度为O(n*logn)
对于堆排序，在此之前我们需要先了解完全二叉树的特性。
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
而二叉树的性质是如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]。那么对于有n个结点的二叉树而言,它的i值自然就是小于等于[n/2]了，即下标i与2i()和2i+1()为双亲子女关系。
而这里我们通过大顶推的方式来实现推排序，而大顶推的类似于，根节点为最大值，每个结点的左右子树都不会大于该结点，利用这样的特性我们可以通过最大的值根节点和最后一个值替换，像叠罗汉一样，然后又通过转化为大顶推的形式将第二大的值放上来继续推出了…
而我们的大顶堆的代码该如何实现呢?这里我们通过定义HeapAdjust函数：
这里就是大顶推的代码实现，而参数L就不用介绍了，参数s为当前结点序号，而m即为数组总长度，而第5行执行的循环中j的值实则为j的右子树，j+1则为左子树，然后迭代下去，第7行则是当j不是最后一个结点且当前结点的左子树<当前结点右子树的时候，让j+1(),如果右子树>当前结点，那么右子树的值将在第11行替换掉当前结点，并将j(右子树的下标)赋值给s，将右子树的位置替换当前结点，然后继续进行下一个根节点左右子树最大值的寻找，如果还不明白可以自行调试。
堆排序完整代码：
这里i的值为长度/2，原因也来自于二叉树的特性，该操作会获取到所以二叉树的根结点下标，通过循环把所有值都转化为了大顶堆，然后在第6行的循环中，用叠罗汉的方式，把当前最大值与最后一个值替换，然后继续调用HeapAdjust函数又转化为大顶堆，以此类推，直到所有循环结束，排序完成。
堆排序的时间复杂度为O(n*logn)
对于归并排序的理解，类似于将一个数组全部拆分出另一个数组，然后在以此数组继续拆分，直到无法拆分后，继续排序，排序完成后将排序完成的数组拼凑回来，然后将排序完成的值返回，该算法用2种实现方法，第一种则是我们最容易想到的递归实现，因为递归和归并非常相似()，而还有一种则是通过非递归实现。
这里整体就是一个递归拆分、排序、重合的过程，我们这里只讲实现排序的Merge函数，该方法获取每一次通过递归一次一次拆分的数组进行排序()，并放入TR中存储着，然后两两分别进行判断，小的往前放，然后最后通过判断将归并剩下的数组移动到TR后面。
对于递归实现的方法，虽然代码容易理解，但是会造成一些时间、空间上的性能损耗。为了提高性能，我们可以通过将递归的方式改为迭代的方式，通过迭代方式修改后性能也会进一步提高。
从代码中可以感受到非递归的迭代归并排序做法非常直截了当，主函数MergeSort2出发，分配空间给TR，然后从索引1开始()，循环条件为当k<当前数组长度，之后调用了MergePass函数，从最小的序列开始归并直至完成。不需要像递归那样先拆分递归，再归并退出，而是执行完毕后将k的值()扩大原来的两倍，继续调用MergePass函数在将k的值加倍…
而我们MergePass函数则是将原来无序的数组两两归并入TR，其中在该函数的n-2*s+1(),而这个s即为k()，而我们为什么要+1呢，其实就是因为两两归并，如果为数组长度为奇数的值，那么定会剩下来，导致无法归并。
而这个Merge函数我们之前在递归实现时讲过这里不讲了，此时的i + s - 1 和i + 2 * s - 1即让SR()中的第一个和第二个记录归并到TR中,然后执行i=i+2*s继续下一个参数归并，直到i<归并范围为止，最后将剩下的序列归并()。
归并排序的时间复杂度为O(n*logn)，所以说归并排序算一种比较占内存、但效率高且稳定的算法。
那么到最后一个，快速排序，快速排序是最早由图灵奖获得者Tony Hoare设计出来的，该算法被称为20世纪十大算法之一，而每一个算法都有其演变的过程，比如我们上面讲的希尔排序相当于直接插入排序的升级，它们同属于插入排序列，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序即为我们前面认为最慢的冒泡排序的升级，它们都属于选择排序类。
而快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
快速排序的思想非常精妙，我们从代码中解析。
在主函数QSort中参数传入的参数分别为数组L()和最小下标值low、最大下标值high，Partition函数的操作为选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大。我们将这样的关键字称为枢轴（pivot）。而后面的递归调用则是对枢轴的左边和右边重复调用Partition函数，直到顺序全部正确为止。
下面我们就来看看快速排序最关键的Partition函数实现是怎么样的。
该函数就是将下标为low()的值当作枢轴记录，然后通过判断与下标为high()的值，如果大于了则不会进行调换，如果low<high，并且下标为high的值>枢轴那么high–()，如果小于则调换位置并将low++()，以此类推直到顺序正确为止。
快速排序的就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
对于快速排序的枢轴而言，每次选取的对象都是第一个的，在某些最坏情况下去查找，会使得效率大大降低，所以就有了三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。
我们来看看取左端、右端和中间三个数的实现代码，在Partition函数上的第3行下面增加这样一段代码。
试想一下，我们对数组{9,1,5,8,3,7,4,6,2}，取左9，中3，右2来比较，使得L.r[low]=3，一定要比9和2要来得更为合理。
三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（median-of-nine），它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的pivotkey是比较接近中间值的关键字。
那么通过上述代码的优化对于Partition函数而言，也可以再进行优化，我们可以将交换改为覆盖替换()，而我们要做的就是通过哨兵()保存枢轴值，那么效率上也会又所提高。
但是对于这些考虑是在数组非常大的情况下才有相对优势，那么在对于数组非常少的时候用这样的方法，那么就像画蛇添足一样了，还不如用之前的方法，所以我们在进行对于这个Qsort函数进行优化。
改进了之后，我们发现该函数是一个递归函数，且还有两次递归回溯，每次回溯都会消耗一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。
于是我们对QSort实施尾递归优化。来看代码：
我们这里通过while(low<high)替换了两次递归的成本。
因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition(L,low,high)，其效果等同于QSort(L,pivot+1,high);。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。
- 简单算法：冒泡、简单选择、直接插入。
- 改进算法：希尔、堆、归并、快速。
从平均情况来看，显然后三种改进算法要胜过希尔排序，并远远胜过前三种简单算法。
从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑四种复杂的改进算法。
从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。