查找、排序
;第9章查找;直接查找算法
IntSearch_Seq(SSTableST,KeyTypekey){
//从尾部依次比较关键字和数据元素旳关键字，
//当比到0下标才成功则查找不成功，返回0
//不然返回下标i
ST.elem[0].key=key;
for(i=ST.length;!EQ(ST.elem[i].key,key);--i);
returni;
}//Search-Seq
0下标监视哨,时间复杂度O(n)
;intSearch_Sq(SSTableST,intkey)
//有序表上顺序查找,监视哨设在高下标端
{
?ST.elem[ST.length+1].key=key;
?for(i=1;ST.elem[i].keykey;i++);
if(iST.length||ST.elem[i].keykey)return0;
?returni;
}//Search_Sq
;折半查找：先拟定待查统计旳范围，逐渐缩小范围直到找到或找不到。
例：在下列数据元素中查找关键字为21和85旳数据元素
分析：设置两个指针low,high指示待查元素所在范围旳上界和下界。mid＝（low+high）/2
ST.elem[mid].key=key:查找成功
ST.elem[mid].keykey：low=mid+1
ST.elem[mid].keykey:high=mid-1
low=high:查找不成功
;intSearch_Bin(SSTableST,KeyTablekey){
//对有序表旳查找采用折半查找，逐渐缩小
//查找范围，直到找到或找不到，返回值为
//找到返回下标，找不到返回0
low=1;high=ST.length;
while(low=high)
{mid=(low+high)/2;
ifEQ(key,ST.elem[mid].key)returnmid;
elseifLT(key,ST.elem[mid].key)
high=mid–1;
elselow=mid+1;
}returnOK;
}//Search_Bin
时间复杂度：O(log2n),
ASL=log2(n+1)+1(按照满二叉树);9.8已知含12个关键字旳有序表及其相应权值如下，画出对下列有序表进行折半查找旳判断树，并计算它旳PH值。;9.9已知如下长度为12旳表，试按表中元素旳顺序依次插入一棵初始为空旳二叉排序树，画出插入完毕后旳二叉排序树，并求其在等概率下查找成功旳平均查找长度。;内部排序;直接插入排序算法：
voidInsertSort(SqListL){
//对顺序表L作直接插入排序，低位（0位）做监视哨
for(i=2;iL.length;++i)
if(L.r[i].keyL.r[i-1].key){
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;L[0].keyL[j].key;--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
};voidInsertSort(SqListL){
//??顺序表L作直接插入排序,以高位(L.length+1)做监视哨
for(i=L.length-1;i1;--i)
if(L.r[i].keyL.r[i+1].key){
L.r[L.length+1]=L.r[i];
L.r[i]=L.r[i+1];
for(j=i+2;L[L.length+1].keyL[j].key;++j)
L.r[j-1]=L.r[j];
L.r[j-1]=L.r[L.length+1];
}
};折半插入排序
查找过程用折半查找措施。
;冒泡排序算法
voidBubbleSort(SqListL){
for(k=L.length-1;k=1;k--)
for(i=0;i=k-1;k++)
if(L.r[i].keyL.r[i+1].key){互换两个统计}
}
时间复杂度：O(n2);49