树形选择排序 (tree selection sort) 详解 及 代码

本文地址: http://blog.csdn.net/caroline_wendy

算法逻辑: 根据节点的大小, 建立树, 输出树的根节点, 并把此重置为最大值, 再重构树.

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

也称锦标赛排序, 时间复杂度为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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; /*树的结构*/ struct BinaryTreeNode{ bool from; //判断来源, 左true, 右false int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; /*构建叶子节点*/ BinaryTreeNode* buildList (const std::vector
        
         & L) { BinaryTreeNode* btnList = new BinaryTreeNode[L.size()]; for (std::size_t i=0; i
         
          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
          
           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
           
             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
            
              temp1; std::queue
             
               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
              
                empty; std::swap(temp2, empty); } } } int main () { std::vector
               
                 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
                
                  result; for (std::size_t i=0; i
                 
                  

                  

                  

                  
输出:
                  

                  
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