12.21

快速排序

int Partition ( SqList L,int low, int high ){
L.elem[0]=L.elem[low];
int pivotkey=L.elem[0];
while(low<high){
while(low<high&&L.elem[high]>=pivotkey) high--;
L.elem[low]=L.elem[high];
while(low<high&&L.elem[low]<=pivotkey) low++;
L.elem[high]=L.elem[low];
}
L.elem[low]=L.elem[0];
return low;
}

 堆排序

void HeapAdjust( HeapType H, int s, int m){
//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆
KeyType rc;
int j;
rc=H.elem[s];
for(j=2*s;j<=m;j*=2)
{//沿key较大的孩子结点向下筛选
if(j<m&&H.elem[j]<H.elem[j+1]) ++j;//j为key较大的记录的下标
if(rc>=H.elem[j]) break; //rc应插入在位置s上
H.elem[s]=H.elem[j]; s=j;
}
H.elem[s]=rc;//插入
}