排序——选择排序

void SelectSort(SqList &L){
	// 对记录序列R[1.. L.length]作简单选择排序
	for(i = 1; i <= L.length; i++){
		// 选择第 i 小的记录，并交换到位
		k = i;
		for(j = i + 1; j <= L.length; ++j)
			if(L.r[j].key < L.r[k].key) k = j;
		if(k != i) Swap(L.r[i], L.r[k]);  // 交换
	}
}

void HeapAdjust(HeapType &H, int s, int m){
	// 已知 H.r [s..m]中记录的关键字除 H.r [s] 之外均
    // 满足堆的特征，本函数自上而下调整 H.r [s] 的
    // 关键字，使 H.r [s..m] 也成为一个大顶堆。
    rc = H.r[s];  // 暂存 H.r [s]
    for(j = 2 * s; j <= m; j *= 2){
    	 // j 初值指向左孩子
    	// 自上而下的筛选过程;
    	if(j < m && H.r[j].key < H.r[j + 1].key) ++j;
    	// 左/右“子树根”之间先进行相互比较
        // 令 j 指示关键字较大记录的位置
        if ( rc.key >= H.r[j].key )  break; 
        // 再作“根”和“子树根”之间的比较，
        // 若“>=”成立，则说明已找到 rc 的插
        // 入位置 s ，不需要继续往下调整
        H.r[s] = H.r[j];   s = j;    
        // 否则记录上移，尚需继续往下调整

    }
    H.r[s] = rc;  // 将调整前的堆顶记录插入到 s 位置
}

void HeapSort ( HeapType &H ) {
	// 对顺序表 H 进行堆排序
	for(i = H.length / 2; i > 0; --i)
		HeapAdjust(H, i, H.length);  // 建大顶堆
	for(i = H.length; i > 1; --i){
		Swap(H.r[1], H.r[i])           
		// 将堆顶记录和当前未经排序子序列
		// H.r[1..i]中最后一个记录相互交换
		HeapAdjust(H, 1, i-1);  // 将H.r[1...i-1]重新调整为大顶堆
	}
}