洞口网站开发公司推荐,怎么盗用网站,平顶山做网站优化,做印刷哪个网站好#x1f921;博客主页#xff1a;Code_文晓 #x1f970;本文专栏#xff1a;数据结构与算法 #x1f63b;欢迎关注#xff1a;感谢大家的点赞评论关注#xff0c;祝您学有所成#xff01; ✨✨#x1f49c;#x1f49b;想要学习更多数据结构与算法点击专栏链接查看博客主页Code_文晓 本文专栏数据结构与算法 欢迎关注感谢大家的点赞评论关注祝您学有所成 ✨✨想要学习更多数据结构与算法点击专栏链接查看✨✨ 在选择类排序中除了我们以往学习过的简单选择排序和堆排序之外比较重点的还有树形选择排序因为这种排序在面试中也偶有出现所以这节课我们也来讲一讲。
1.1 基本概念与算法描述
树形选择排序又叫锦标赛排序Tournament Sort是一种按照锦标赛的思想进行选择排序的方法。属于对简单选择排序的一种改进。
我们尝试描述一下树形选择排序算法对n个记录的关键字进行两两比较。然后在其中 ⌈⌉ 个较小者中再进行两两比较如此重复直到选出最小关键字按从小到大排序为止。
以数组 { 16,1,45,23,99,2,18,67,42,10 } 为例参考图1。 图1从下向上观察这是第一趟排序目的是从所有数组中选出值最小的元素。我们尝试描述下具体的操作步骤。 开始两两比较于是元素16和1比较选择1元素45和23比较选择23元素99和2比较选择218和67比较选择1842和10比较选择10。 现在选择出的元素1、23、2、18、10又进行两两比较元素1和23比较选择1元素2和18比较选择2元素10没有比较的对象直接被选择。 现在选择出的元素1、2、10又进行两两比较元素1和2比较选择1元素10没有比较的对象直接被选择。 现在选择出的元素1、10又进行比较选择1。最终这个1也是树形结构的树根找个地方保存本趟排序的最小元素1。
接着在树叶中把第一趟已经选择出的元素1标记为一个最大值 ∞这表示元素1不可能在比较中被再次选中了然后进行第二趟排序如图2所示。 图2还是从下向上观察这是第二趟排序前面挑选出的最小值1已经找了个地方保存这里直接把1的值修改为一个最大值∞这样对节点进行两两比较时标记为最大值的节点就不可能被选中。第二趟排序需要进行什么比较呢 开始两两比较元素16和最大值比较选择元素16。元素45和23、99和2、18和67、42和10就不需要再次比较因为第一趟排序比较过了。 现在选择出的元素16和23比较选择元素16。元素2和18元素10同样因为第一趟比较过不需要再次比较。 现在选择出的元素16和2比较元素10同样因为第一趟比较过不需要再次比较。 现在选择出的元素2、10进行比较选择2。最终这个2也是树形结构的树根找个地方保存本趟排序的最小元素2。
然后继续把第二趟中已经选择出的元素2标记为一个最大值就可以开始第三趟排序这里就不赘述了。
所以可以看到经过一次第一趟的完全比较后从第二趟开始就不再需要完全的两两比较这样就达到了节省时间提高效率的目的这就是树形选择排序相较于简单选择排序一个重大的改进之处。但是也应该看到树形选择排序需要通过构造出二叉树这种树形结构来辅助排序所以还需要辅助存储空间。
上述图1和图2意在阐述树形选择排序理论理论上来说树形选择排序并不复杂。但若通过代码实现则是需要构建一棵完全二叉树来实现对数据排序的。换句话说图1和图2绘制得比较简单很多额外的节点并没有绘制出来。
回忆一下二叉树的性质5——具有nn0个节点的完全二叉树的高度为 ⌈⌉ 或者 ⌊⌋ 1。同时你也需要知道含有n个叶子节点的完全二叉树的高度是 ⌈⌉ 1。以这个理论为指导为了能够正确编写出代码绘制一下更详细的树形选择排序示意图。依旧以数组 { 16,1,45,23,99,2,18,67,42,10 } 举例来解释树形选择排序。 把该数组中的所有元素都看成是完全二叉树的叶子根据“含有n个叶子节点的完全二叉树的高度是 ⌈⌉ 1”树形选择排序所要创建的这棵完全二叉树高度应该是5。 第一趟两两比较找到最小值保存到根节点中如图3所示。 接着沿着根节点向叶子节点找找到了最小值1所在的叶子节点把该叶子节点的值从原来保存的1修改为最大值 ∞如图4所示。 接着要开始第二趟比较了第二趟比较时叶子节点之间不再需要两两比较只需要16和∞作比较此时当然是16更小于是沿着这个比较路线再前进到树根就能把当前树中的最小节点找到并保存到根中。如图5所示。 接着沿着根节点向叶子节点找找到了最小值2所在的叶子节点把该叶子节点的值从原来保存的2修改为最大值 ∞如图6所示。 持续上述步骤就可以把整个数据序列按从小到大的顺序排列好。
1.2 实现代码
下面我给出树形选择排序的实现代码。
#define INT_MAX_MY 2147483647//整型能够保存的最大数值作为标记使用
//树形选择排序从小到大
templatetypename T
void TreeSelSort(T myarray[], int length)
{//ceil是系统函数ceil(x)函数返回的是大于或等于x的最小整数int treelvl (int)ceil(log(length) / log(2)) 1; //5:完全二叉树高度(含有n个叶子节点的完全二叉树的高度是⌈logn⌉ 1)//treelvl高的完全二叉树最多有nodecount个节点如果有nodecount个节点此时的完全二叉树其实是满二叉树int nodecount (int)pow(2, treelvl) - 1; //31满二叉树是指一棵高度为h且含有2h-1个节点的二叉树//treelvl-1 高的完全二叉树最多有nodecount2个节点int nodecount2 (int)pow(2, treelvl - 1) - 1; //15int* pidx new int[nodecount];//保存节点的下标用的内存//叶子节点保存元素的下标值就等于保存了元素的值for (int i 0; i length; i){pidx[nodecount2 i] i; //pidx[15] 0; pidx[16] 1....;pidx[24] 9} //end for//给多余的叶子节点赋予一个最大值作为标记for (int i nodecount2 length; i nodecount; i) //i25~30{pidx[i] INT_MAX_MY; //pidx[25] MAX;pidx[26] MAX; ......pidx[30] MAX}int tmpnode2 nodecount2; //15int tmpnode nodecount; //31//现在要开始给非叶子节点赋值了,非叶子节点下标是[0]~[14]//第一趟排序要给非叶子节点赋值还要两两进行节点比较所以要单独处理while (tmpnode2 ! 0){//第一次for执行i值分别为15、17、19、21、23、25、27、29//第二次for执行i值分别为7,9,11,13//第三次for执行i值分别为3,5//第四次for执行i值分别为1for (int i tmpnode2; i tmpnode; i 2){//第一次for这个pidx的下标【(i 1) / 2 - 1】分别是7,8,9,10,11,12,13,14//第二次for这个pidx的下标【(i 1) / 2 - 1】分别是3,4,5,6//第三次for这个pidx的下标【(i 1) / 2 - 1】分别是1,2//第四次for这个pidx的下标【(i 1) / 2 - 1】分别是0//把两个孩子中小的孩子值给爹if (pidx[i] ! INT_MAX_MY pidx[i 1] ! INT_MAX_MY) //如果pidx[i]和pidx[i1]都是正常值那自然是可以比较{if (myarray[pidx[i]] myarray[pidx[i 1]]){pidx[(i 1) / 2 - 1] pidx[i];}else{pidx[(i 1) / 2 - 1] pidx[i 1];}}else if( pidx[i] ! INT_MAX_MY) //pidx[i]是正常值因为有上个if在说明pidx[i 1]不是正常值{pidx[(i 1) / 2 - 1] pidx[i];}else //走到这里说明pidx[i 1]是正常值或者是INT_MAX_MY值{pidx[(i 1) / 2 - 1] pidx[i 1];}} //end fortmpnode tmpnode2; //15,7,3,1tmpnode2 (tmpnode2 - 1) / 2; //7,3,1,0} //end whileT* ptmparray new T[length]; //临时保存排好序的数据for (int i 0; i length; i){ptmparray[i] myarray[pidx[0]]; //将当前最小值赋给ptmparray[i]临时保存int leafidx 0;//沿树根找最小值结点在叶子中的序号//leafidx 0,1,3,7,16分别追溯到叶子中的编号for (int j 1; j treelvl; j){if (pidx[2 * leafidx 1] pidx[leafidx]){leafidx 2 * leafidx 1;}else{leafidx 2 * leafidx 2;}} //end for j//此时的leafidx就是完全二叉树叶子节点中的那个最小值的下标pidx[leafidx] INT_MAX_MY; //leafidx 16。while (leafidx){//leafidx 7,3,1,0leafidx (leafidx 1)/2 - 1;//序号为leafidx的结点的双亲结点序号if (pidx[2 * leafidx 1] ! INT_MAX_MY pidx[2 * leafidx 2] ! INT_MAX_MY) //如果pidx[i]和pidx[i1]都是正常值那自然是可以比较{if (myarray[ pidx[2 * leafidx 1]] myarray[pidx[2 * leafidx 2]]){pidx[leafidx] pidx[2 * leafidx 1];}else{pidx[leafidx] pidx[2 * leafidx 2];}}else if (pidx[2 * leafidx 1] ! INT_MAX_MY){pidx[leafidx] pidx[2 * leafidx 1];}else{pidx[leafidx] pidx[2 * leafidx 2];}}//end while} //end for i//把数据从ptmparray拷贝回myarrayfor (int i 0; i length; i){myarray[i] ptmparray[i];} //end for i//释放内存delete[] ptmparray;delete[] pidx;return;
}在main主函数中加入测试代码。
int arr[] {16,1,45,23,99,2,18,67,42,10};
int length sizeof(arr) / sizeof(arr[0]); //数组中元素个数
TreeSelSort(arr, length);//对数组元素进行树形选择排序
cout 树形选择排序结果为;
for (int i 0; i length; i)
{cout arr[i] ;
}
cout endl; //换行
代码的执行结果如下 树形选择排序算法因为含有n个叶子节点的完全二叉树的高度是 ⌈⌉ 1除了最小关键字外每次选择其他最小关键字只需要 ⌈⌉ 次比较因为还有 n-1 个关键字需要进行这个次数的比较所以可以认为该算法的时间复杂度是 O()。 对于算法的空间复杂度在上述实现代码中是需要一些辅助空间帮忙实现排序的空间换时间比如存储完全二叉树节点还可能需要存储其他一些数据比如临时的排好序的数据。当然也可以用其他办法而不是必须用临时空间保存排好序的数据不过总体来看树形选择排序的空间复杂度为O()。 此外经过我测试认为上述算法的实现代码是稳定的。如果你稍微调整一下其实现代码改为不稳定的也很容易。
1.3 小结 这节课我们一起学习了选择类排序中的树形选择排序。树形选择排序是一种按照锦标赛的思想进行选择排序的方法属于对简单选择排序的一种改进。它会通过多趟排序来对 n 个记录的关键字进行两两比较然后在其中 ⌈⌉ 个较小者中再进行两两比较如此重复直到选出最小关键字按从小到大排序为止。 树形选择排序的每一趟排序都会减少需要两两比较的元素数量从而达到了节省时间提高效率的目的这就是树形选择排序相较于简单选择排序一个重大的改进之处。 但是我们也应该看到树形选择排序需要通过构造出二叉树这种树形结构来辅助排序所以还需要辅助存储空间。 这篇文章我们也详细解释了树形选择排序的概念通过多个示意图对该排序的算法进行了详尽的描述也为你提供了完整的实现代码。最后强调一个细节树形选择排序算法的时间复杂度是 O()空间复杂度为 O()算法是稳定的。
