数据结构：堆排序

爱被打了一巴掌 2022-05-31 12:53 230阅读 0赞

# 堆排序 #

就是构建堆，然后取出堆顶元素即可

# 代码如下 #

#include<iostream>
    #include<ctime>
    #include<cstdlib>
    using namespace std;
    
    
    void adjust(int* a,int index,int SIZE);
    void HeapSort(int* a,int SIZE);
    void swap(int* a,int x,int y);
    void print(int* a,int SIZE);
    void insertHeapSort(int * a,int SIZE);
    void insert(int * a,int SIZE);
    
    
    int main()
    {
        srand(time(0));
        const int SIZE=20;
        int * a=new int[SIZE];
        for(int i=0;i<SIZE;i++)
            a[i]=(random()%(2*SIZE));
        HeapSort(a,SIZE);
    }
    
    //堆得插入
    void insertHeapSort(int* a,int SIZE)
    {
        for(int i=0;i<SIZE;i++)
        {
             a[i]=(int)random()%(2*SIZE);
             insert(a,i+1);
        }
    
    
        for(int i=SIZE-1;i>=0;i--)
        {
            swap(a,0,i);
            adjust(a,0,i);
        }
    
        cout<<"AFTER "<<endl;
        print(a,SIZE);
    
    }
    
    
    //堆得插入一个元素
    void insert(int* a,int SIZE)
    {
        int key=a[SIZE-1];
        int i=SIZE-1;
        cout<<SIZE<<endl;
        while(i>=0)
        {
        //只要是比父节点打的话,都要向上替换
            int par=(i-1)/2;
            if(par>=0 && a[par] < key)
            {
                 a[i]=a[par];
                  i=par;
            }
            else
                break;
    
        }
        a[i]=key;
    }
    
    void swap(int* a,int x,int y)
    {
        int tmp=a[x];
        a[x]=a[y];
        a[y]=tmp;
    }
    
    void print(int* a,int SIZE)
    {
        for(int i=0;i<SIZE;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    
    //递归向下调整
    void adjust(int* a,int index,int SIZE)
    {
        //选择左孩子和右孩子和目前节点的最大值
        int le=2*index+1;
        int ri=le+1;
        //下面的小于是构造最小堆,换成大一就是构造最大堆
        int maxIndex=(le<SIZE && a[le] > a[index]) ? le : index;
        maxIndex=(ri<SIZE && a[ri] > a[maxIndex]) ? ri : maxIndex;
    
        if(maxIndex!=index)
        {
            swap(a,maxIndex,index);
            adjust(a,maxIndex,SIZE);
        }
    
    
    }
    
    void HeapSort(int* a,int SIZE)
    {
        cout<<"BEFORE "<<endl;
        print(a,SIZE);
        //SIZE-1 表示最后一个元素,(index-1) / 2 表示父节点
        for(int i=((SIZE-1)-1)/2;i>=0;i--)
        {
            adjust(a,i,SIZE);
        }
    
        for(int i=SIZE-1;i>=0;i--)
        {
            swap(a,0,i);
            adjust(a,0,i);
        }
    
        cout<<"AFTER "<<endl;
        print(a,SIZE);
    }

其实我建议这么做，这样更加清楚明了。在整理成最大堆的时候，相当于从(len-1)/2节点向下调整，删除堆顶元素的时候相当于从0向下调整，这样做更加方便，也好记

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    
    void adjust(vector<int>& a, int i, int len)
    {
        int tmp = 0;
        for (; 2 * i + 1 < len; i = tmp)
        {
            tmp = 2 * i + 1;
            if (tmp + 1 < len && a[tmp + 1] > a[tmp])
                tmp += 1;
            if (a[i] < a[tmp])
                swap(a[i], a[tmp]);
            else
                break;
        }
    
    }
    
    int main()
    {
        vector<int> a;
        for (int i = 0; i < 10; i++)
            a.push_back(10 - i);
    
        for (int i : a)
            cout << i << "  ";
        cout << endl;
    
        for (int i = (a.size() - 1) / 2; i >= 0; i--)
            adjust(a, i, a.size());
    
        for (int i = 0; i < a.size(); i++)
        {
            swap(a[0], a[a.size() - 1 - i]);
            adjust(a, 0, a.size() - i - 1);
        }
    
        for (int i : a)
            cout << i << "  ";
        cout << endl;
        system("pause");
    }