首页 / 软件开发 / 数据结构与算法 / C++实现树形选择排序 （tree selection sort）

C++实现树形选择排序 （tree selection sort）2015-10-12算法逻辑: 根据节点的大小, 建立树, 输出树的根节点, 并把此重置为最大值, 再重构树.

因为树中保留了一些比较的逻辑, 所以减少了比较次数.

也称锦标赛排序, 时间复杂度为O（nlogn）, 因为每个值（共n个）需要进行树的深度（logn）次比较.

参考<数据结构>（严蔚敏版） 第278-279页.

树形选择排序（tree selection sort）是堆排序的一个过渡, 并不是核心算法.

但是完全按照书上算法, 实现起来极其麻烦, 几乎没有任何人实现过.

需要记录建树的顺序, 在重构时, 才能减少比较.

本着娱乐和分享的精神, 应人之邀, 简单的实现了一下.

代码:

/** 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, 右falseint 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 49Round[1] : 27 38 27 38 65 76 27 49 38 65 97 76 MAX 27 49Round[2] : 38 38 49 38 65 76 49 49 38 65 97 76 MAX MAX 49Round[3] : 49 49 49 49 65 76 49 49 MAX 65 97 76 MAX MAX 49Round[4] : 49 65 49 MAX 65 76 49 MAX MAX 65 97 76 MAX MAX 49Round[5] : 65 65 76 MAX 65 76 MAX MAX MAX 65 97 76 MAX MAX MAXRound[6] : 76 97 76 MAX 97 76 MAX MAX MAX MAX 97 76 MAX MAX MAXRound[7] : 97 97 MAX MAX 97 MAX MAX MAX MAX MAX 97 MAX MAX MAX MAXRound[8] : MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAX MAXresult : 13 27 38 49 49 65 76 97

作者：csdn博客 Caroline-Wendy