排序的基本概念

按数据存储介质：内部排序和外部排序

按比较器个数：串行排序和并行排序

按主要操作：比较排序和基数排序

插入排序：

基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

基本操作：有序插入

直接插入排序---采用顺序查找法查找插入位置

1. 复制插入元素

2. 记录后移，查找插入位置

3. 插入到正确位置

直接插入排序：使用“哨兵”

1. 复制为哨兵

2. 记录后移，查找插入位置

3. 插入到正确位置

时间复杂度：O(n²)

折半插入排序：查找插入位置时采用折半查找法

折半查找比顺序查找快

希尔排序：

基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

特点：缩小增量，多遍插入排序

空间复杂度：O(1)

时间复杂度是n和d的函数：O(n^1.25)~O(1.6n^1.25)

是一种不稳定的排序方法

冒泡排序：每趟不断将记录两两比较，并按“前小后大”规则交换

时间复杂度：

最好情况（正序）：比较次数：n-1；移动次数：0

最坏情况（逆序）：比较次数：1/2（n²-n）；移动次数：3/2（n²-n）

快速排序：

基本思想：

任取一个元素为中心；

所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；

对各子表重新选择中心元素并依此规则调整；

直到每个子表的元素只剩一个

具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。

快速排序是一种不稳定的排序方法。

简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。

堆排序：

堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点

归并排序：

基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列

在内部排序中，通常采用的是2-路归并排序。

基数排序：

基本思想：分配+收集

也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。

基数排序：数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百...进行排序