基于选择排序方法的类模板设计与实现c课程设计(编辑修改稿)

基于选择排序方法的类模板设计与实现c课程设计(编辑修改稿)内容摘要：

late class Type void SortType::tree_select_sort(Type arr[],int n) //树形选择排序 5 { 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])。 6 } 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 + 1] ? tree[maxIndex] : tree[maxIndex + 1])。 } else // 如果不是左子结点 { // 用子结点中较大值代替父结点 tree[maxIndex / 2] = (tree[maxIndex] tree[maxIndex 1] ? tree[maxIndex] : tree[maxIndex 1])。 7 } maxIndex /= 2。 // 继续处理父结点 } } } template class Type void SortType::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(jnamp。 amp。 array[j]array[j+1]) //若有孩子较大，把 j 指向右孩子 j=j+1。 if(temparray[j]) { array[i]=array[j]。 //array[j]调整到双亲结点 i=j。 j=2*i。 } else break。 } array[i]=temp。 } template class Type void SortType::HeapSort(Type ar[]) //堆排序 { int i。 8 Type t。 for(i=len/2。 i=1。 i) //循环建立初始堆 AdjustTree(array,i,len)。 for(i=len。 i=2。 i) //进行 n1 次循环，完成堆排序 {t=array[i]。 array[i]=array[1]。 array[1]=t。 AdjustTree(array,1,i1)。 } } templateclass Type void SortType::write() //输入数组 { int i,l。 printf(请输入数组长度 :)。 scanf(%d,amp。 l)。 len=l。 printf(请输入数组元素 :\n)。 for(i=1。 i=l。 i++) cinarray[i]。 } templateclass Type void SortType::print() //输出数组 {int i。 printf(排序后的数组为 :\n)。 for(i=1。 i=len。 i++) coutarray[i]。 coutendl。 } 9 在类的成员函数实现过程中， 系统会自动为类产生构造函数， 类的构造函数自动 调用，为 类 动态分配了内存空间 ， 整个调用过程中完全是由系统内部完成。 成员函数对成员变量进行操作， 实现排序功能，通过 for( ) 循环，实现输入输出数组元素的功能。 主函数设计 在程序的主函数部分，选择了 分别以 int、 char 和 float 型为数据类型的对象作为 实际例子来验证算法。 首先，选择数据类型 ； 然后，通过 write( ) 函数对成员变量数组 array[ ] 进行赋值，通过 swich（）。