8.1 排序的基本概念
后续内容针对的存储结构如下：
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
经验：写算法是画出一个具体的数组，填写上值和下标，根据实际例子来写程序。
以下是对 “high+1则为插入位” 的解释
以下是实际例子
其实上面这个过程就是折半查找最基本的思想，只是因为这里是折半查找的最后一个循环，high和low交错，所以要难以理解一点。
8.2.3 希尔排序
问题：第二个for循环的 j>0 是否可以去掉？哨兵的作用不就是省略掉边界判断语句吗。
对这段程序的解释： 当dk=1，希尔排序也就是等于之前的直接插入排序。
8.3 交换排序
8.3.1 冒泡排序
8.3.2 快速排序
8.4 选择排序
8.4.1 简单排序
8.4.2 堆排序
说明：
先比较左右孩子，找出较大的那一个，用 j 指向它；
如果这个较大的孩子大于双亲，则让它和双亲交换，否则循环结束；
更新双亲结点到下一层；
重复以上操作。
重点注意注释判断语句的注释！
//调整大顶堆
void HeapAdj(SqList& L, int s, int m) {//s：每一次调整的堆顶 m：每一次调整的堆尾
//简单讲，就是将孩子结点较小的放到双亲位置
int top = L.r[s].key;
for (int j = 2 * s; j <= m; j = j * 2) {// j 的初值指向左孩子 注意！！！j可以等于m，不然对于两个节点构成的堆就无法进行调整！！！！！！！！！
if ( j+1<=m && L.r[j].key < L.r[j + 1].key) j = j + 1;// j 最终需要指向孩子中较大的那个 j+1<=m 必不可少！！！以防右孩子超出边界
if (top >= L.r[j].key) break;//堆顶本身就大，则不需要交换
else{
L.r[s].key = L.r[j].key;
L.r[j].key = top;
s = j;
top = L.r[s].key;
}
}
}
从最后一个非叶子结点开始，最后一个非叶子节点的位置=n/2。
具体过程看视频p169
8.5 归并排序
这叫做“归并树”，是一颗倒着的树，树的深度为log2n
8.6 基数排序
特点：适用于关键字的取值范围确定的，且关键字的种类较少的。
8.7 排序总结
