这道题大概就是要实现一个数组,这个数组中行所有元素都有序,列所有元素都有序。
其实这也是应用堆排序的思想,就是把这个数组的看做是二叉树组成的。一个元素的下面一行的对应一个元素是它的左孩子,右边一个元素是它的右孩子。
这样就可以应用堆排序来解决这个问题了。
同时也是像堆排序一样,实际使用一维数组存储数据,人为规定(按照堆排序的规则,这个是关键思维)地构造二维数组来存储二叉树。
详细程序如下:
#include<iostream>
#include<vector>
using namespace std;
int gChildren = 2;
int column = 4;
//实际用以为数组表示数据,但是通过人为地规定,构造了一个二维数组,同理可以很轻松地构造三维数组
//主要不同之处就是寻找孩子和父母节点不一样了
int youngTableauUpParent(int cIndex) //cIndex 为C下标0开始
{
return cIndex-column;
}
int youngTableauleftParent(int cIndex)
{
return cIndex-1;
}
int youngTableauChild(int cIndex, int leftOrRight) //cIndex 为C下标0开始
{
if(leftOrRight==1)//代表左孩子
return cIndex+column;
else //代表是右孩子
return cIndex+1;
}
//找出当前节点和其孩子们的当中的最大值;
//本人觉得是本人创造的非常妙的从youngTableauify函数中分离出来的功能函数。极大的简化了对本算法的理解。
template<typename T>
int youngTableauMax(vector<T>& youngTableau, int cIndex, int youngTableauSize)
{
T tempMax = youngTableau[cIndex];
int childIndex = 0;
int tempIndex = cIndex;
//不同处:如果是最右一列就没有右孩子,如果是最下面一行就没有左孩子,就直接跳过
if(youngTableauChild(cIndex, 1)<youngTableauSize)
{
childIndex = youngTableauChild(cIndex, 1);//1代表左孩子
if(youngTableau[childIndex]>tempMax)
{
tempMax = youngTableau[childIndex];
tempIndex = childIndex;
}
}
//注意:少了第二个判断条件会出现错误结果,而且很难Debug。千万不能漏了条件
if((cIndex+1)%column!=0 && (cIndex+1)<youngTableauSize)
{
childIndex = youngTableauChild(cIndex, 2);//2代表右孩子
if(youngTableau[childIndex]>tempMax)
{
tempMax = youngTableau[childIndex];
tempIndex = childIndex;
}
}
return tempIndex;
}
//与堆排序一模一样
//We assume cIndex's children have all been youngTableauified, which is the key to make this algorithm work!!!
//比之前的二叉树堆排序更加简洁明了点
template<typename T>
void youngTableauify(vector<T>& youngTableau, int cIndex, int youngTableauSize)
{
if(cIndex<youngTableauSize)
{
int tempIndex = youngTableauMax(youngTableau, cIndex, youngTableauSize);
if(tempIndex != cIndex)
{
swap(youngTableau[cIndex], youngTableau[tempIndex]);
youngTableauify(youngTableau, tempIndex, youngTableauSize);
}
}
}
template<typename T>
void buildMaxyoungTableau(vector<T>& youngTableau)
{
for(int i=(youngTableau.size()-1); i>=0; i--) //不同处:从下表倒数第二个开始
youngTableauify(youngTableau, i, youngTableau.size());
}
//与堆排序一模一样
template<typename T>
void youngTableauSort(vector<T>& youngTableau)
{
buildMaxyoungTableau(youngTableau);
for(int i=youngTableau.size()-1; i>0; i--)
{
swap(youngTableau[0], youngTableau[i]);
youngTableauify(youngTableau, 0, i);
}
}
template<typename T>
void youngTableauPrint(const vector<T>& youngTableau)
{
int i = 1;
for(auto x:youngTableau)
{
cout<<x<<"\t";
if(i%column==0) cout<<endl;
i++;
//输出格式化的数组,方便检查
}
cout<<endl;
}
void test()
{
//初始化数组
int a[15] = {2,4,7,1,4,8,9,31,83,28,48,94,87,16,36};
vector<int> youngTableau(a, a+15);
//序列输出
cout<<"Befor build youngTableau:\n";
youngTableauPrint(youngTableau);
//建立大顶堆后输出
cout<<"After build youngTableau:\n";
buildMaxyoungTableau(youngTableau);
youngTableauPrint(youngTableau);
//排序后
cout<<"After sort:\n";
youngTableauSort(youngTableau);
youngTableauPrint(youngTableau);
}
int main()
{
test();
return 0;
}
结果:
可以改变column,以改变列数,来看看结果如何,而且最后一行可以是不满列,列如本例中column等于4的时候:
column = 3:
column = 4:
可以是任意列数,甚至可以是column=1,column=100,会有有趣的结果哦,呵呵。有兴趣的可以试一试,想想为什么。
分享到:
相关推荐
中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部
算法导论----算法经典书籍----不用我多做介绍了吧。算法导论----算法经典书籍----不用我多做介绍了吧。
上学时 一些算法导论的代码----矩阵连乘,弗洛伊德,bellman 01背包 n皇后
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
算法导论作业-->Introduction to algrithms:homework
算法导论 算法导论 算法导论 算法导论 算法导论 算法导论 算法导论 算法导论 算法导论
算法经典书籍,算法导论-Cormen-完整中文版-带书签,第2版影印版
算法导论的讲义、习题答案,与公开课视频相对应(视频去网易公开课找),搭配视频一起学习,效果非常,强烈推荐!
算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar算法导论课件-经典.rar
麻省理工的算法导论,值得一读,是算法入门的绝好文档,欢迎大家下载
算法导论第三版练习题15.2-2的C++实现方案
计算机算法导论--教师手册 英文原版 计算机专业必读书
[算法导论].[Introduction.to.Algorithms].Thomas.H.Cormen.Ronald.L.Rivest.Charles.E.Leiserson.Clifford.Stein.文字版.pdf
算法导论 算法导论 算法导论 算法导论 算法导论 算法导论算法导论 算法导论 算法导论
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
算法导论上的堆排序c++源程序||学习分享
算法-理论基础- 排序- 堆排序(包含源程序).rar
算法导论习题集,这本书是算法导论每小节后习题的分析讲解,很详细,值得学习!
算法导论:每一个程序设计师都需要掌握的书籍
算法导论第三版课后习题答案 只有部分的答案