基于选择排序方法的类模板设计与实现C++课程设计

{

Type tree[M]; // 树

int baseSize; // 当n是2的幂次时,baseSize是n, 当n不是时,baseSize是大于n的最小的2的幂次

// 就是构造成满二叉树的最下层的大小，即叶子数 int i;

Type max; // 最大值

int maxIndex; // 最大数的下标

int treeSize; // 最终这棵树会达到的大小

baseSize = 1; while (baseSize < n) {

baseSize *= 2; }

treeSize = baseSize * 2 - 1;//满二叉树的所有结点个数等于叶子数的2倍减一

for (i = 0;i < n;i++) // 从数组的后面部分开始填充, 不使用tree[0] {

tree[treeSize - i] = arr[i]; }

for (;i < baseSize;i++) // 用MIN_VALUE填充tree,直到一共有baseSize个 {

tree[treeSize - i] = MIN_VALUE; }

// 构造一棵树

for (i = treeSize;i > 1;i -= 2) {

// 以arr[i]和arr[i + 1]为子结点的数的根是arr[i]和arr[i + 1]中的较大者 tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);

5

}

n = n - 1; //此时的n表示当前tree[1]应该放到arr中的位置 // 不断把树中值为最大值的结点移走,直到n的值为-1

while (n != -1) {

max = tree[1]; arr[n--] = max; maxIndex = treeSize;

// 在叶子上找到最大值对应的下标 while (tree[maxIndex] != max) {

maxIndex--; }

tree[maxIndex] = MIN_VALUE; // 沿着叶子上的结点到根的路径更新 while (maxIndex > 1) // 当结点还有父结点时 {

if (maxIndex % 2 == 0) // 如果值为最大值的结点是左子结点 {

// 用子结点中较大值代替父结点

tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + tree[maxIndex] : tree[maxIndex + 1]);

}

else // 如果不是左子结点 {

// 用子结点中较大值代替父结点

tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - tree[maxIndex] : tree[maxIndex - 1]);

6

? ? 1] 1] }

maxIndex /= 2; // 继续处理父结点 } } }

template

void Sort::AdjustTree(Type ar[],int k,int n) //调整堆 { int i,j; i=k;

j=2*i; //arrau[j]是array[i]的左孩子 Type temp=array[i]; while(j<=n)

{if(j

array[i]=array[j]; //array[j]调整到双亲结点 i=j; j=2*i;

} else break; }

array[i]=temp; }

template

void Sort::HeapSort(Type ar[]) //堆排序 { int i;

7

Type t;

for(i=len/2;i>=1;i--) //循环建立初始堆

AdjustTree(array,i,len);

for(i=len;i>=2;i--) //进行n-1次循环，完成堆排序 {t=array[i]; array[i]=array[1]; array[1]=t;

AdjustTree(array,1,i-1); } }

template

void Sort::write() //输入数组 { int i,l;

printf(\请输入数组长度:\scanf(\len=l;

printf(\请输入数组元素:\\n\for(i=1;i<=l;i++) cin>>array[i]; }

template

void Sort::print() //输出数组 {int i;

printf(\排序后的数组为:\\n\ for(i=1;i<=len;i++) cout<

8