数据结构与算法(十五)排序算法
排序算法是最基本的算法之一，也是平时最常见、最常用的算法。
1、排序的稳定性
对于一个未排序的序列， 其中a[2]和a[5]的关键字值相等，经过排序后，若原a[2]的位置仍在原a[5]之前，那么称该排序方法是稳定的；若原a[5]的位置反在原a[2]的前面，那么称该排序方法是不稳定的。
只要有一组关键字发生类似的情况，便认为此排序方法不稳定。排序算法是否稳定，需要通过仔细分析才能得出。
举个栗子：未排序前令狐冲和张无忌的总分是一样的，令狐冲的排名在张无忌之前，经过排序后，若令狐冲的排名仍在张无忌之前，那么该排序方法就是稳定的；若令狐冲的排名在张无忌的后面，那么该排序方法就是不稳定的。
2、排序的方式
根据在排序过程中待排序的记录是否全部被放在内存中，将排序方式分为：内排序和外排序。
内排序是在排序整个过程中，待排序的所有记录全部被放在内存中。
外排序是由于待排序记录个数太多，不能同时放在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。
内排序算法的性能主要受三个方面的影响：
1、时间性能：排序算法的时间开销是衡量其好坏的最重要标志，主要进行两种操作：比较和移动。高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
2、辅助空间：执行算法所需要的辅助存储空间的大小。
3、算法复杂度：这里是指算法本身的复杂度，而不是时间复杂度。算法本身过于复杂也会影响排序性能。