C++锦标赛排序算法改进
看了东南大学那个算法视频，知道了锦标赛排序算法的原理，在网上搜了一下，实现的比较少代码也不够规范。先简要说一下原理：锦标赛算法是选择排序改进的，充分利用前面选择最小值的比较步骤，去除后面冗余的比较。比如你在前一遍已经比较出了
a1<a2了，后面你应该想直接用这个结果，而不是再比较一次，因此这些比较值存储于一颗完全二叉树中，这棵树记载了两两比较的结果，这样，
前面比较之后，就可以利用前面的结果进行比较，而且只需要遍历上次改动的一个分支。将最小的节点逐层比较通过0号元素输出，并把这个元素
对应于原数组在二叉树中的位置标记为无穷大，并从该叶节点的父节点开始比较，这样循环直到全部输出为止。原视频中说存储的直接是值，然而
实际操作中发现并不方便，因为根据值不好判断他的索引是什么，去除的时候也不是随便去除而是找你产生最小值的分支进行去除，否则会出错。
我这种方法在二叉树中记录的是索引，元素的去除就会将索引标记为一个特殊的数。如果是内建的排序算法，那么你可以直接吧这个位置并到数组中，
将该索引位置的值赋值为无穷大，但是考虑到通用性，我没有这么做，于是就要判断索引值是否合法了。如果内建的算法的话，效率估计会更高。
代码如下：
// test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void main()
{
const int size=17;
int data;
int j;
int k;
for(k=0;k<size;k++)
{
data=rand()&0xFF;
printf("%d ",data);
}
printf("\n");
#define MAX 256//只要比数组大就可以
vector<int> treedata;//二叉树
int volumn=2;
while(volumn < size)
volumn *= 2;
int newsize=volumn-1+size;//计算完全二叉树容量
vector<int> copydata;
treedata.resize(newsize);
for(int i=0;i < volumn-1;i++)
{
treedata=MAX;//根据需要调整该值，只要大于原数组容量即可
}
for(i=0;i<size;i++)
{
treedata=i;
}
for(j=0;j<newsize;j++)
{
cout<<treedata<<" ";
}
cout<<endl;
cout<<"newsize:"<<newsize<<endl;
//生成初始树总长度为newsize
for(i=volumn-2;i >= 0;i--)
{
if(i*2+1 < newsize && treedata != MAX)//有左子树且合法
{//如果没有左子树，根据完全二叉树性质，肯定没有右子树，同理初始化时，如果左子树为MAX，那么右子树一定是MAX
int tochange=i*2+1;
if(i*2+2 < newsize && treedata != MAX)//如果有右子树
{
if(data] < data])
tochange=i*2+2;
}
treedata=treedata;
}
}
int left=size;
while(left--) //做size次
{
if(left == 8)
{
int a=0;
cout<<treedata<<endl;
cout<<data]<<endl;
}
copydata.push_back(data]);
int index=volumn-1+treedata;//索引位置
treedata=MAX;
//从索引位置往父节点递归
do
{
index = (index-1)/2;//得到父节点
treedata=MAX;//重置父节点
if(index*2+1 < newsize)//有左子树
{//仍然是如果没有左子树肯定没有右子树
int tochange=index*2+1;//可能为MAX
if(index*2+2 < newsize && treedata != MAX)
{
if(treedata == MAX ||
(treedata != MAX && data] > data]))
tochange=index*2+2;
}
treedata=treedata;//可能赋值为MAX
}
}
while(index);
}
for(j=0;j<newsize;j++)
{
cout<<treedata<<" ";
}
cout<<endl;
for(j=0;j<copydata.size();j++)
{
data=copydata.at(j);
}
printf("\n");
for(k=0;k<size;k++)
{
printf("%d ",data);
}
printf("\n");
getchar();
}
页:
[1]