08-排序
目录
8.1排序概念
8.2插入排序
Ⅰ.直接插入排序
Ⅱ.折半插入排序
Ⅲ.希尔排序
8.3交换排序
Ⅰ.冒泡排序
Ⅱ.快速排序
8.4选择排序
Ⅰ.简单选择排序
Ⅱ.堆排序
8.5归并排序
8.6基数排序
*各种排序方法的比较
8.1排序概念
排序：将无序序排成有序序列
内部排序：数据量不大，数据在内存，无需内外存交换数据
外部排序：数据量较大，数据在外存
（外部排序时要将数据分批调入内存来排序，中间结果还要及时放入外存，这比内部排序复杂的多）
串行排序：单处理机（同一时刻比较一对元素）
并行排序：多处理机（同一时刻比较多对元素）
比较排序：用比较的方法
基数排序：不比较元素大小，仅仅根据元素本身的取值确定其有序的位置
原地排序：辅助空间用量为O(1)的排序方法（非原地排序：超过O(1)）
（原地排序所占辅助存储空间与参加排序的数据量大小无关）
稳定排序：能够使任何数值相等的元素，排序以后相对次序不变
（排序的稳定性只对结构类型数据排序有意义）
（排序是否稳定，并不能衡量一个排序算法的优劣）
自然排序：输入数据越有序，排序速度越快
8.2插入排序
有序插入，在有序序列中插入一个元素，保持序列有序，有序长度不断增加
Ⅰ.直接插入排序
由上图我们可以看出，每插入一个元素都要判断下标越界，这很浪费时间
我们在这里使用“哨兵”来解决上述问题：将要插入的元素复制为哨兵，放到0的位置
算法思路：将要插入的元素首先与最后一个元素比较，如果本身比最后一个元素大就不用移动了，否则则将元素设为哨兵依次向前比较，直到遇到比自身小的元素，插入在该元素的下一个位置，之后的元素依次后移
最好的情况就是元素在记录序列中顺序有序，这样就不用移动了
如果有n个元素，最好情况下的比较次数就为n-1（第一个不用比较）
同理，最坏的情况就为逆序有序，所需的次数如下
Ⅱ.折半插入排序
1）折半查找比顺序查找快
2）折半查找所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象的个数
3）折半查找对象的移动次数与顺序查找相同，依赖于对象的初始排列
Ⅲ.希尔排序
算法思想：
特点：①缩小增量②多边插入排序
示例 ：
8.3交换排序
Ⅰ.冒泡排序
每趟不断将记录两两比较，并按“前小后大”规则交换
一旦某趟比较时不出现记录交换，说明已经排好了，可以结束了
（后续几趟同理）
1）n个记录总共需要n-1趟（最多的情况下）
2）第m趟需要比较n-m次
优点：每趟结束时，不仅能挤出一个最大值到最后面的位置，还能同时部分理顺其他元素
Ⅱ.快速排序
是一种改进的交换排序，是一种不稳定排序
上面这种方法太浪费空间了，在算法中不可取
特点：1）每一趟的子表的形成是采用从两头向中间交替式逼近法
2）由于每趟中对子表的操作都类似，可采用递归算法
在算法中采用这种方法
当low和high重合时，一趟结束，将届点放在low的位置，函数返回low的值（位置）
8.4选择排序
从未排序序列中挑选元素，并将其依次放入已排序列（初始时为空）的一端的方法
Ⅰ.简单选择排序
在待排序的数据中选出最大（小）的元素放在其最终位置，是一种不稳定排序
Ⅱ.堆排序
堆排序的初始化操作：将待排序列构造成一个大根堆
对应由n个元素组成的无序序列，“筛选”只需要从第n/2个元素开始（即保证它是双亲，如上图中的62）
堆排序仅需一个记录大小供交换用的辅助存储空间
8.5归并排序
8.6基数排序
这里的k不是直接相乘的意思，而是表示几组相加
n是元素个数，m在例题中是10（0~9），要分配几趟，k就是几，在例题中是3
再来一道例题便于理解
*各种排序方法的比较
