C++锦标赛排序算法改进

元始天尊

    看了东南大学那个算法视频，知道了锦标赛排序算法的原理，在网上搜了一下，实现的比较少代码也不够规范。
先简要说一下原理：锦标赛算法是选择排序改进的，充分利用前面选择最小值的比较步骤，去除后面冗余的比较。比如你在前一遍已经比较出了
a1<a2了，后面你应该想直接用这个结果，而不是再比较一次，因此这些比较值存储于一颗完全二叉树中，这棵树记载了两两比较的结果，这样，
前面比较之后，就可以利用前面的结果进行比较，而且只需要遍历上次改动的一个分支。将最小的节点逐层比较通过0号元素输出，并把这个元素
对应于原数组在二叉树中的位置标记为无穷大，并从该叶节点的父节点开始比较，这样循环直到全部输出为止。原视频中说存储的直接是值，然而
实际操作中发现并不方便，因为根据值不好判断他的索引是什么，去除的时候也不是随便去除而是找你产生最小值的分支进行去除，否则会出错。
我这种方法在二叉树中记录的是索引，元素的去除就会将索引标记为一个特殊的数。如果是内建的排序算法，那么你可以直接吧这个位置并到数组中，
将该索引位置的值赋值为无穷大，但是考虑到通用性，我没有这么做，于是就要判断索引值是否合法了。如果内建的算法的话，效率估计会更高。
代码如下：

1. // test.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. #include "stdafx.h"
   
5. 
   
6. #include <stdio.h>
   
7. #include <stdlib.h>
   
8. #include <iostream>
   
9. #include <stack>
   
10. #include <vector>
    
11. using namespace std;
    
12. 
    
13. void main()
    
14. {
    
15.         const int size=17;
    
16.         int data[size];
    
17. 
    
18.         int j;
    
19.         int k;
    
20.        
    
21.         for(k=0;k<size;k++)
    
22.         {
    
23.                 data[k]=rand()&0xFF;
    
24.                 printf("%d ",data[k]);
    
25.         }
    
26.         printf("\n");
    
27.        
    
28. 
    
29. #define MAX 256//只要比数组大就可以
    
30.         vector<int> treedata;//二叉树
    
31.         int volumn=2;
    
32. 
    
33.         while(volumn < size)
    
34.                 volumn *= 2;
    
35. 
    
36.         int newsize=volumn-1+size;//计算完全二叉树容量
    
37. 
    
38.         vector<int> copydata;
    
39. 
    
40.         treedata.resize(newsize);
    
41.         for(int i=0;i < volumn-1;i++)
    
42.         {
    
43.                 treedata[i]=MAX;//根据需要调整该值，只要大于原数组容量即可
    
44.         }
    
45. 
    
46.         for(i=0;i<size;i++)
    
47.         {
    
48.                 treedata[i+volumn-1]=i;
    
49.         }
    
50. 
    
51.         for(j=0;j<newsize;j++)
    
52.         {
    
53.                  cout<<treedata[j]<<" ";
    
54.         }
    
55.         cout<<endl;
    
56.         cout<<"newsize:"<<newsize<<endl;
    
57. 
    
58.         //生成初始树  总长度为newsize
    
59.         for(i=volumn-2;i >= 0;i--)
    
60.         {
    
61.                 if(i*2+1 < newsize && treedata[i*2+1] != MAX)//有左子树且合法
    
62.                 {//如果没有左子树，根据完全二叉树性质，肯定没有右子树，同理初始化时，如果左子树为MAX，那么右子树一定是MAX
    
63.                         int tochange=i*2+1;
    
64.                         if(i*2+2 < newsize && treedata[i*2+2] != MAX)//如果有右子树
    
65.                         {
    
66.                                 if(data[treedata[i*2+2]] < data[treedata[tochange]])
    
67.                                         tochange=i*2+2;
    
68.                         }
    
69.                         treedata[i]=treedata[tochange];
    
70.                 }
    
71.         }
    
72. 
    
73.         int left=size;
    
74.         while(left--) //做size次
    
75.         {
    
76.                 if(left == 8)
    
77.                 {
    
78.                         int a=0;
    
79.                         cout<<treedata[0]<<endl;
    
80.                         cout<<data[treedata[0]]<<endl;
    
81.                 }
    
82.                 copydata.push_back(data[treedata[0]]);
    
83.                 int index=volumn-1+treedata[0];//索引位置
    
84.                 treedata[index]=MAX;
    
85.                 //从索引位置往父节点递归
    
86.                 do
    
87.                 {
    
88.                         index = (index-1)/2;//得到父节点
    
89.                         treedata[index]=MAX;//重置父节点
    
90. 
    
91.                         if(index*2+1 < newsize)//有左子树
    
92.                         {//仍然是如果没有左子树肯定没有右子树
    
93.                                 int tochange=index*2+1;//可能为MAX
    
94.                                 if(index*2+2 < newsize && treedata[index*2+2] != MAX)
    
95.                                 {
    
96.                                         if(treedata[tochange] == MAX ||
    
97.                                                         (treedata[tochange] != MAX && data[treedata[tochange]] > data[treedata[index*2+2]]))
    
98.                                                 tochange=index*2+2;
    
99.                                 }
    
100.                                 treedata[index]=treedata[tochange];//可能赋值为MAX
     
101.                         }
     
102.                 }
     
103.                 while(index);
     
104.         }
     
105. 
     
106.         for(j=0;j<newsize;j++)
     
107.         {
     
108.                 cout<<treedata[j]<<" ";
     
109.         }
     
110.         cout<<endl;
     
111. 
     
112. 
     
113.         for(j=0;j<copydata.size();j++)
     
114.         {
     
115.                 data[j]=copydata.at(j);
     
116.         }
     
117.         printf("\n");
     
118. 
     
119. 
     
120.         for(k=0;k<size;k++)
     
121.         {
     
122.                 printf("%d ",data[k]);
     
123.         }
     
124.         printf("\n");
     
125.        
     
126.         getchar();
     
127. }
     
128. 
     

复制代码