排序：对一序列对象依据某个keyword进行排序；

稳定：假设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操作，直到无序区为空为止。

优势：移动次数较少。但比較次数同样。

堆排序：

目的：降低比較的次数。

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

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

算法例如以下：

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

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

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

（1）假设结点i的关键码大。则全然二叉树已经是堆，筛选完成。   

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

对照图：