树形选择排序(tree selection sort)是堆排序的一个过渡,并不是核心算法,大家可以结合介绍和C++代码的范例进行理解。
(1)算法介绍
树形选择排序(Tree Selection Sort),又称锦标赛排序(Tournament Sort),是一种按锦标赛的思想进行选择排序的方法。简单选择排序花费的时间主要在比较上,每次都会进行很多重复的比较,造成浪费时间。锦标赛排序就是通过记录比较结果,减少比较次数,从而降低时间复杂度。
(2)算法描述
首先对n个记录的关键字进行两两比较,然后再对胜者进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树描述。
(3)算法分析
1. 时间复杂度:O(NlogN)
2. 空间复杂度:O(N)
3. 稳定性:稳定(依赖于具体实现)
4. 缺点:辅助存储空间较多,和∞的比较多余。
为了弥补这些缺点,威洛姆斯(J·willioms)在1964年提出了另一种形式的选择排序——堆排序。
(4)标准锦标赛排序原理:
对N个记录的关键字进行两两比较,选出最小(大)的n/2个数,再进行新一轮的比较,直到选出最小(大)的。
1. 把N个数放到完全二叉树的叶子节点,两两比较,选出最小的作为根节点,且保存到数组中
2. 把最小的原始值设为无穷大,从那个地方开始新一轮比较
注:第一次比较n-1,后面都是log2(n)次
(5)C++代码实现如下:
/* * TreeSelectionSort.cpp * * Created on: 2014.6.11 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <iostream> #include <vector> #include <stack> #include <queue> #include <utility> #include <climits> using namespace std; /*树的结构*/ struct BinaryTreeNode{ bool from; //推断来源, 左true, 右false int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; /*构建叶子节点*/ BinaryTreeNode* buildList (const std::vector<int>& L) { BinaryTreeNode* btnList = new BinaryTreeNode[L.size()]; for (std::size_t i=0; i<L.size(); ++i) { btnList[i].from = true; btnList[i].m_nValue = L[i]; btnList[i].m_pLeft = NULL; btnList[i].m_pRight = NULL; } return btnList; } /*不足偶数时, 需补充节点*/ BinaryTreeNode* addMaxNode (BinaryTreeNode* list, int n) { /*最大节点*/ BinaryTreeNode* maxNode = new BinaryTreeNode(); //最大节点, 用于填充 maxNode->from = true; maxNode->m_nValue = INT_MAX; maxNode->m_pLeft = NULL; maxNode->m_pRight = NULL; /*复制数组*/ BinaryTreeNode* childNodes = new BinaryTreeNode[n+1]; //添加一个节点 for (int i=0; i<n; ++i) { childNodes[i].from = list[i].from; childNodes[i].m_nValue = list[i].m_nValue; childNodes[i].m_pLeft = list[i].m_pLeft; childNodes[i].m_pRight = list[i].m_pRight; } childNodes[n] = *maxNode; delete[] list; list = NULL; return childNodes; } /*依据左右子树大小, 创建树*/ BinaryTreeNode* buildTree (BinaryTreeNode* childNodes, int n) { if (n == 1) { return childNodes; } if (n%2 == 1) { childNodes = addMaxNode(childNodes, n); } int num = n/2 + n%2; BinaryTreeNode* btnList = new BinaryTreeNode[num]; for (int i=0; i<num; ++i) { btnList[i].m_pLeft = &childNodes[2*i]; btnList[i].m_pRight = &childNodes[2*i+1]; bool less = btnList[i].m_pLeft->m_nValue <= btnList[i].m_pRight->m_nValue; btnList[i].from = less; btnList[i].m_nValue = less ? btnList[i].m_pLeft->m_nValue : btnList[i].m_pRight->m_nValue; } buildTree(btnList, num); } /*返回树根, 又一次计算数*/ int rebuildTree (BinaryTreeNode* tree) { int result = tree[0].m_nValue; std::stack<BinaryTreeNode*> nodes; BinaryTreeNode* node = &tree[0]; nodes.push(node); while (node->m_pLeft != NULL) { node = node->from ? node->m_pLeft : node->m_pRight; nodes.push(node); } node->m_nValue = INT_MAX; nodes.pop(); while (!nodes.empty()) { node = nodes.top(); nodes.pop(); bool less = node->m_pLeft->m_nValue <= node->m_pRight->m_nValue; node->from = less; node->m_nValue = less ? node->m_pLeft->m_nValue : node->m_pRight->m_nValue; } return result; } /*从上到下打印树*/ void printTree (BinaryTreeNode* tree) { BinaryTreeNode* node = &tree[0]; std::queue<BinaryTreeNode*> temp1; std::queue<BinaryTreeNode*> temp2; temp1.push(node); while (!temp1.empty()) { node = temp1.front(); if (node->m_pLeft != NULL && node->m_pRight != NULL) { temp2.push(node->m_pLeft); temp2.push(node->m_pRight); } temp1.pop(); if (node->m_nValue == INT_MAX) { std::cout << "MAX" << " "; } else { std::cout << node->m_nValue << " "; } if (temp1.empty()) { std::cout << std::endl; temp1 = temp2; std::queue<BinaryTreeNode*> empty; std::swap(temp2, empty); } } } int main () { std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49}; BinaryTreeNode* tree = buildTree(buildList(L), L.size()); std::cout << "Begin : " << std::endl; printTree(tree); std::cout << std::endl; std::vector<int> result; for (std::size_t i=0; i<L.size(); ++i) { int value = rebuildTree (tree); std::cout << "Round[" << i+1 << "] : " << std::endl; printTree(tree); std::cout << std::endl; result.push_back(value); } std::cout << "result : "; for (std::size_t i=0; i<L.size(); ++i) { std::cout << result[i] << " "; } std::cout << std::endl; return 0; }
如果我们编译并运行上述程序,那么它应该产生以下结果:
Begin : 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49 Round[1] : 27 38 27 38 65 76 27 49 38 65 97 76 MAX 27 49 Round[2] : 38 38 49 38 65 76 49 49 38 65 97 76 MAX MAX 49 Round[3] : 49 49 49 49 65 76 49 49 MAX 65 97 76 MAX MAX 49 Round[4] : 49 65 49 MAX 65 76 49 MAX MAX 65 97 76 MAX MAX 49 Round[5] : 65 65 76 MAX 65 76 MAX MAX MAX 65 97 76 MAX MAX MAX Round[6] : 76 97 76 MAX 97 76 MAX MAX MAX MAX 97 76 MAX MAX MAX Round[7] : 97 97 MAX MAX 97 MAX MAX MAX MAX MAX 97 MAX MAX MAX MAX Round[8] : MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX result : 13 27 38 49 49 65 76 97
知识点标签:排序
本文固定URL:https://www.dotcpp.com/course/940
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程