PHP数据结构（十七） ——内部排序综述
PHP数据结构（十七）——内部排序综述
（原创内容，转载请注明来源，谢谢）
一、稳定性
假设Ki=Kj(1<=i,j<=n,i!=j)，且排在序列前的序列中Ri领先于Rj（即i>j）。
1）若在排序后的序列中，Ri必然仍领先于Rj，则称所用的排序方法是稳定的。
2）如果Ri可能出现在Rj之后的情况，则称所用的排序方法是不稳定的。
用一句话描述，就是原数组中两个相同的数字，一个在前一个在后，经过某种排序后（无论重新使用该方法排序多少次），仍一个在前一个在后，则称为稳定。
二、排序方式
区分方式：待排序记录数量不同，使的排序过程中涉及的存储器不同。
1）内部排序
待排序记录数量较少，存放于计算机随机存储器中进行排序。
2）外部排序
待排序记录数量较多，内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问。
三、内部排序分类
大致分为五类：插入排序、交换排序、选择排序、并归排序、计数排序。其中，时间复杂度可以分为三种：
1）简单排序方法，时间复杂度O(n2)
2）先进排序方法，时间复杂度O(nlogn)
3）基数排序方法，是将复杂度O(d*n)
四、排序过程
排序过程通常进行两个操作：
1）比较两个关键字的大小。
2）将记录从一个位置移动至另一个位置。
待排序记录有下列三种存储方式：
1）待排序的一组记录存放在地址连续的一组存储单元上，类似于线性表的顺序存储结构，序列中相邻的两个记录存储位置也相邻，排序需要借助移动记录。
2）（链）表排序：待排序的一组记录存放在静态链表中，记录的次序由指针指示，实现排序不需要移动记录，只需要修改指针即可。
3）地址排序：待排序记录本身存储在一组地址连续的存储单元内，另设一个指示各记录存储位置的地址向量，在排序过程中不移动记录本身，而是移动地址向量中记录的这些地址，拍些虚侯按照地址向量的值调整记录的存储位置。
五、各种内部排序方法比较
如下表所示：
排序方法 | 平均时间 | 最坏情况 | 辅助存储 |
|---|---|---|---|
简单排序 | O(n2) | O(n2) | O(1) |
快速排序 | O(nlogn) | O(n2) | O(logn) |
堆排序 | O(nlogn) | O(nlogn) | O(1) |
并归排序 | O(nlogn) | O(nlogn) | O(n) |
基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(rd) |
1）平均性能而言，快速排序最佳，但最坏情况下不如堆排序和并归排序。堆排序和并归排序比较，n较大时并归排序所需时间较堆排序少，但所需的辅助存储量多。
2）简单排序包括除希尔排序之外的所有插入排序，冒泡排序，简单选择排序。当序列中的记录基本有序或n值较小时，用直接插入排序最佳，因此其可以和快速排序、并归排序结合在一起用。
3）基数排序时间复杂度也可以写成O(d*n)，适用于n值很大而关键字较小的序列。如果关键字也很大，序列中大多数记录最高为关键字均不同，则也可以先按最高位关键字不同将序列分成若干小的子序列，再用直接插入进行排序。
4）稳定性比较
基数排序、简单排序都是稳定的，快速排序、堆排序、希尔排序不稳定。
一般而言，排序如果是通过比较相邻的关键字，则排序方法是稳定的，否则是不稳定的。稳定的排序，无论使用多少次，结果都是稳定的；不稳定的排序，经过多次使用后，总会出现不稳定的情况。
5）经过推论，借助于比较进行排序的算法，最坏情况下能达到最好的时间复杂度是O(nlogn)。
——written by linhxx 2017.07.16