maxheap.h

有各种排序算法

#include"DataList.h"
template <class T>
void siftDown (dataList<T>& L,const int left,const int right) {
	int i = left,   j = 2*i+1;  	   //j 是 i 的左子女位置
	Element<T> temp = L[i];                    //
	while (j <= right) {		             //检查是否到最后
		if (j < right && L[j] < L[j+1] ) j++;    
		//j 取两子女中大者
		if (temp >= L[j]) break;
		//大则不做调整
		else { L[i] = L[j];  i = j; j = 2*j+1; }
		//否则小者上移, i, j下降
	}
	L[i] = temp; 	  	//回放temp中暂存的元素
};
template <class T>
void HeapSort (dataList<T>& L) {
//对表L.Vector[0]到L.Vector[n-1]进行排序, 使得表
//中各个元素按其排序码非递减有序
    int i, n = L.GetSize();
    for (i = (n-2)/2; i >= 0; i--) 	//将表转换为堆
        siftDown (L, i, n-1);	     //先调整成初始堆
    for (i = n-1; i > 0; i--) {   //对表排序,或改为i >= 1
        L.Swap(L[0], L[i]);  siftDown (L, 0, i-1); //交换与调整
    }    //教材有误
};