数据结构课设个人（七）：堆排序

对于顺序存储的线性表，使用vector或数组，实现堆排序算法，并输出每趟的排序结果。

参考函数原型：（vector版本）

（1）//建堆 

template

void HeapSort( vector &A, int flag ); //flag：堆类型标记

（2）//堆调整（最大堆） 

template

void HeapASCAdjust( vector &A, int hole, int size );

（2）//堆调整（最小堆） 

template

void HeapDASCAdjust( vector &A, int hole, int size );

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）

第二行：堆类型标记（1：大根堆，2：小根堆）

第三行：待排序顺序表A的数据元素（数据元素之间以空格分隔）

如第一行输入值为0、1、2、3之外的值，直接输出“err”

否则：

第一行：第一趟的排序结果（数据元素之间以","分隔）

第三行：第二趟的排序结果（数据元素之间以","分隔）

...

第n行：最终的排序结果（数据元素之间以","分隔）

0
1
21 25 49 25 93 62 72 8 37 6 54

93,54,72,37,25,62,49,8,25,6,21
72,54,62,37,25,21,49,8,25,6,93
62,54,49,37,25,21,6,8,25,72,93
54,37,49,25,25,21,6,8,62,72,93
49,37,21,25,25,8,6,54,62,72,93
37,25,21,6,25,8,49,54,62,72,93
25,25,21,6,8,37,49,54,62,72,93
25,8,21,6,25,37,49,54,62,72,93
21,8,6,25,25,37,49,54,62,72,93
8,6,21,25,25,37,49,54,62,72,93
6,8,21,25,25,37,49,54,62,72,93

• 堆排序是一种树型选择排序，在排序过程中，将R[1]到R[n]看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（i的左孩子为2*i；右孩子为2*i+1）来选择关键字最小记录。
• 两种类型：  (1) 小根堆(根结点值小于或等于左右孩子的值)（2）大根堆(根结点值大于或等于左右孩子的值)。
• 难点：将堆的当前顶点输出后，如何将剩余序列重新调整为堆。
  方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整，如此反复直至排序结束。
• 建堆步骤：从最后一个非终端结点（n/2下取整）开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。

    堆的第一个对象r[0]具有最大的关键码，将r[0]与r[n]对调，把具有最大关键码的对象交换到最后;
    再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即r[0]位置;
    再对调r[0]和r[n-1]，然后对前n-2个对象重新调整，…如此反复，最后得到全部排序好的对象序列。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include    //用于ostringstream、istringstream、stringstream这三个类
#include
#include
#include
#include
using namespace std;
template
void createvector( vector &A )
{
    ElemType tmp;
    string temp;
    getline(cin,temp);
    stringstream input(temp); //输入流
    while(input>>tmp)
        A.push_back(tmp);
}
//堆调整（最大堆）
template
void HeapASCAdjust( vector &A, int root, int length ){  //从第root个元素到第length个元素建堆
      int current=root,child=current*2;//初始设置i为左子树根节点
  //  ElemType temp=A[root-1];  //记录当前根节点值
    while(child<=length){  检查是否到达当前堆尾，未到尾则整理
        if(childA[child-1])
            child+=1;//令child为子树中最大值序号
        if(A[child-1]
void HeapDASCAdjust( vector &A, int root, int length ){
    int current=root,child=current*2;//初始设置i为左子树根节点
  //  ElemType temp=A[root-1];  //记录当前根节点值
    while(child<=length){  检查是否到达当前堆尾，未到尾则整理
        if(child
void HeapSort( vector &A, int flag ){ //flag：堆类型标记（1：大根堆，2：小根堆）
   int length=A.size();
    if(flag==1){
        for(int i=length/2;i>=1;--i) // length/2下取整是最后一个完全二叉树非终端节点
            HeapASCAdjust( A, i, length);   //建立初始堆,从下往上建立，每次都把以第i个元素为根节点的树调整为大根堆
        int m=length;
        for(int i=0;i=1;--i)
            HeapDASCAdjust( A, i, length);
        int m=length;
        for(int i=0;i>kd;
    cin.ignore();
    int flag;
    cin>>flag;
    cin.ignore();
    if(kd==0){
        vector A;
        createvector( A );
        HeapSort( A, flag );
    }
    else if(kd==1){
        vectorA;
        createvector( A );
        HeapSort( A, flag );
    }
    else if(kd==2){
         vectorA;
         createvector( A );
         HeapSort( A, flag );
    }
     else if(kd==3){
        vectorA;
        createvector( A );
         HeapSort( A, flag );
     }
    else
        cout<<"err"<