希尔排序，快速排序，堆排序

绝代码农

插入排序：有序插入
希尔排序：
基本思想:先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
特点：
一次移动，移动位置较大，跳跃式地接近排序后的最终位置
最后一次只需要少量移动
增量序列必须递减，最后一个必须是1
增量序列必须是互质的。
Hibbard增量序列：Dk=2^k-1----相邻元素互质
Sedgewick增量序列：{1，5，19，41，109}
主程序：

void ShellSort(Sqlist &L, int dlta[], int t)
{
//按增量序列dlta[0...t-1]对顺序表L作希尔排序
int k;
for (k = 0; k < t; ++k)
{
ShellInsert(L, dlta[k]);//一趟增量为dlta[k]的插入排序
}
}//ShellSort

每一步进行的操作

void ShellInsert(Sqlist &L, int dk)
{//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
int i, j;
for (i = dk + 1; i <= L->length; i=i+dk)
{
if (L->r[i].key < L->r[i - dk].key)
{
L->r[0] = L->r[i];
for (j = i - dk; j>0 && (L->r[0].key < L->r[j].key); j = j - dk)
L->r[j + dk] = L->r[j];
L->r[j + dk] = L->r[0];
}
}
}

快速排序：
基本思想：任取一个元素（如：对一个）为中心
所有比它小的元素往前放，比它大的往后放，形成两个子表
对子表选择中心元素并依此规则调整，
直到每个子表的元素只剩一个
主程序，递归进行排序：

void QSort(Sqlist &L, int low, int high)
{
int pivotloc;
if (low < high)//长度》1
{
pivotloc = Partition(L, low, high);
//将L.r[low..high]一分为2，pivotloc为枢轴元素排好序的位置
QSort(L, low, pivotloc - 1);//对低子表递归排序
QSort(L, pivotloc + 1, high);//对高子表递归排序
}//endif
}//QSort

将中心点放在合适位置：

int Partition(Sqlist &L, int low, int high)
{
int pivotkey;
L->r[0] = L->r[low];
pivotkey = L->r[low].key;
while (low < high)
{
while (low < high&&L->r[high].key >= pivotkey)--high;//比较后面部分，直到遇到比中心点小的
L->r[low] = L->r[high];
while (low < high && L->r[low].key <= pivotkey)++low;//换前面
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low;
}

堆排序：
堆实质是满足如下性质的完全二叉树：二叉树中任一叶子结点均小于（大于）根结点
堆排序：若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）。。。。如此反复，便能得到一个有序序列，这个过程称之为堆排序
堆的调整：
1.输出堆顶元素之后，以堆中最后一个元素替代之
2.然后将根结点值与左，右子树的根节点值进行比较，并与其中小者进行交换；
3.重复1，2，直至叶子节点，将得到新的堆，称这个过程为”筛选“

void HeapAdjust(elem R[], int s, int m)
{//R[s...m]中的关键字除了R[s]外均满足堆定义，本函数调整R[s]的关键字，使R[s...m]成为一个小根堆
int rc,j;
rc = R[s];
for (j = 2 * s; j <= m; j *= 2)//沿key较小的孩子结点向下筛选
{
if (j<m&&R[j]>R[j + 1])++j;//j为key较小的记录下标
if (rc <= R[j])break;
R[s] = R[j]; s = j;//rc应插入在s位置
}//for
R[s] = rc;//插入
}//HeapAdjust

建堆：
调整：
从最后一个非叶子结点开始，向前调整：
1，调整从第n/2个元素开始，将该元素为根的二叉树调整为堆
2，将n/2-1的结点为根的二叉树调整为堆
。。。。。

for (int i = n / 2; i >= 1; i--)
HeapAdjust(R, i, n);