排序法总结与比较

排序：对一序列对象根据某个关键字进行排序；

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

            例如：插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序

不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

                例如：希尔排序、快速排序、选择排序、堆排序

内排序：不占用额外内存或占用常数的内存；

                例如：插入排序、选择排序、冒泡排序、堆排序、快速排序。

外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

                 例如：归并排序、计数排序、基数排序、桶排序。

基于比较的排序：主要是通过关键记录的比较和移动来实现。其时间复杂度下限为nlog(n)；

不基于比较的排序：通常没有大量的比较和移动操作。

排序关键的操作为：比较、移动；

排序分类：

(1)交换类：冒泡排序、快速排序；此类的特点是通过不断的比较和交换进行排序；

(2)插入类：简单插入排序、希尔排序；此类的特点是通过插入的手段进行排序；

(3)选择类：简单选择排序、堆排序；此类的特点是看准了再移动；

(4)归并类：归并排序；此类的特点是先分割后合并；

最坏情况就是逆序

最好情况就是顺序

历史进程：一开始排序算法的复杂度都在O(n^2)，希尔排序的出现打破了这个僵局；

插入排序：

1、划分。将序列分为有序区和无序区两部分。初始化时，有序区为第一个记录；

2、插入。将无序区的第一个记录插入到有序区中；

3、一直循环2的操作，直到无序区没有记录为止。

适用于：序列中记录较少，序列基本有序

希尔排序：

1、分割为子序列。等间隔跳跃分割为子序列，在子序列内进行插入排序；

2、一直循环1操作，直到间隔大于等于1为止。

冒泡排序;

1、划分。将序列分为有序区和无序区两部分。初始化时，有序区为空；

2、冒泡。从后向前两两比较，反序则交换；

3、一直循环2操作，直到无序区为空为止。

快速排序：

序列越随机，算法复杂度越低。不管是正序还是逆序，都是其最坏情况。

1、将i 和 j 分别指向待排序区域的最左侧记录和最右侧记录，并选取第一个记录为轴数；

2、重复下述过程，直到 i = j ：

（1）右侧扫描，直到记录 j 小于轴数； 如果 i < j，则将 r[j] 与 r[i] 交换，并将 i++； 

（2）左侧扫描，直到记录 i 大于轴数； 如果 i < j，则将 r[i] 与 r[j] 交换，并将 j--；

3、退出循环，说明i和j指向了轴数，返回该位置

4、递归。对轴数前段、后段子序列分别执行上述操作，直到子序列中只含有1个元素为止。

选择排序：

1、划分。将序列分为有序区和无序区两部分。初始化时，有序区为空；

2、选择。在无序区中选择最小的记录，将它与无序区的第一个记录交换，使有序区扩展了一个记录。

3、一直循环2操作，直到无序区为空为止。

优势：移动次数较少，但比较次数相同。

堆排序：

目的：减少比较的次数。

         堆排序实际是一棵以顺序方式存储的完全二叉树。

满足以下性质：树中任一非叶子结点的关键字不大于（或不小于）其左右孩子结点的关键字。

算法如下：

1、设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子； 

2、若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右孩子结点（如果有右孩子），并将j指向关键码较大的结点； 

3、将要筛选结点i的关键码与j所指向的结点的关键码进行比较   

（1）如果结点i的关键码大，则完全二叉树已经是堆，筛选完毕；   

（2）否则将r[i]与r[j]交换；令i=j，转步骤2继续进行筛选；

对比图：