数据结构实验--堆排序

﹏ヽ暗。殇╰゛Y 2024-03-30 11:30 41阅读 0赞

**目录**

堆排序

代码

运行结果

--------------------

## 堆排序 ##

*  ### 代码 ###

/*
        堆排序
    */
    
    #include<iostream>
    using namespace std;
    
    /*
        堆调整算法
    */
    void Sift(int *data,int n,int k, int last)
    {
        int i, j, temp;
        i = k; j = 2 * i + 1;  // i是被筛选结点，j是i的左孩子
        while (j <= last) //筛选还没有进行到叶子
        {
            if (j < last && data[j] < data[j + 1]) j++;     // j指向左右孩子的较大者
            if (data[i] > data[j])
                break;               //已经是堆
            else
            {
                temp = data[i]; data[i] = data[j]; data[j] = temp;
                i = j; j = 2 * i + 1;  //被筛结点位于原来结点j的位置
            }
        }
    }
    
    
    /*
        堆排序算法
    */
    void HeapSort(int data[],int n)
    {
        int i, temp;
        
        for (i = ceil(n / 2) - 1; i >= 0; i--)       //从最后一个分支结点至根结点
            Sift(data,n,i, n - 1);
        for (i = 1; i < n; i++)
        {
            temp = data[0]; data[0] = data[n - i]; data[n - i] = temp;
            Sift(data,n,0, n - i - 1);                          //重建堆
        }
    }
    
    int main() {
        int length=0, data[10];
        cout << "请输入10个数：" << endl;
        for (int i=0; i < 10; i++) {
            cin >> data[i];
            ++length;
        }
    
        cout << "这十个数为：" << endl;
        for (int k = 0; k < length; k++) {
            cout << data[k] << "\t";
        }
        cout << endl;
        cout << "堆排序结果为：" << endl;
    
        HeapSort(data,length);
        for (int j = 0; j < length; j++) {
            cout << data[j]<<"\t";
        }
        cout << endl;
    
        return 0;
    }

*  ### 运行结果 ###

![a597c3cadf0c436698197e08b32604cc.png][]

[a597c3cadf0c436698197e08b32604cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d829faabfaa34791842d3f006fb424f4.png