{
L.arr[j + dk] = L.arr[j]; //记录后移，查找插入位置}//end for j
L.arr[j + dk] = L.arr[0]; //插入
}//end if
}//end for i
}//shellInsert
//按增量序列dlta[0...t-1]对顺序表做希尔排序
voidshellSort(SqList&L, intdlta[], int t)
{
for (int k = 0;k < t; k++)
{
shellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入序列}
}
//折半插入排序
voidbInsertSort(SqList&L)
{
for (int i = 2; i <= L.length; i++){
L.arr[0] = L.arr[i];//将其暂存到arr[0]
int low = 1;
int high = i - 1;
while(low <= high){//在arr[low...high]中折半查找有序插入的位置int m = (low + high) / 2;//折半
if(L.arr[0].key high = m - 1;//插入点在低半区
else low = m + 1;//插入点在高半区
}//while
for(int j = i - 1; j >= high + 1; j--)
L.arr[j + 1] = L.arr[j];//记录后移
L.arr[high + 1] = L.arr[0];//插入
}//for
}//BInsertSort
//直接插入排序
voidinsertSort(SqList&L)
{
for(int i = 2; i <= L.length; i++){
if(L.arr[i].key L.arr[i] = L.arr[i-1];
int j;
for(j = i - 2; L.arr[0].key L.arr[j+1] = L.arr[j];//记录后移
L.arr[j+1] = L.arr[0];//插入到正确位置
}//if
}//for
}//InsertSort
//冒泡排序
voidbubbleSort(SqList&L)
{
RedType* temp = NULL;
for(int i = 1; i for(int j = 1; j <= L.length-i; j++){//第j次排序
if(L.arr[j].key >L.arr[j+1].key){
//交换前后的位置
L.arr[0] = L.arr[j];
L.arr[j] = L.arr[j+1];
L.arr[j+1] = L.arr[0];
}//if
}//for j
}//for i
}//bubbleSort
//交换顺序表中子表L.arr[low...high]的记录,
//枢轴记录到位,并返回其所在位置
int partition(SqList&L, int low, int high)
{
L.arr[0] = L.arr[low];//子表的第一个记录做枢轴记录
KeyTypepivotKey = L.arr[low].key;//枢轴记录关键字
while(low < high){//从表的两端交替向中间扫描
while(low < high &&L.arr[high].key >= pivotKey){
high--;
}//while
L.arr[low] = L.arr[high];//将比枢轴小的记录移到低端
while(low < high &&L.arr[low].key <= pivotKey){
low++;
}//while
