数据结构-排序综合（堆排序）

利用随机函数产生N个随机整数（200以上），对这些数进行由小到大排序。要求：采用堆排序

需要程序与运行结果截图

好了

#include <stdio.h>
#include <stdlib.h>

void heapadjust(int* a, int n, int i) {
    int t, c;
    for (t = a[i]; 2 * i + 1 < n; i = c) {
        c = 2 * i + 1;
        if (c < n - 1 && a[c] < a[c + 1])
            c++;
        if (a[c] > t) {
            a[i] = a[c];
            a[c] = t;
        } else
            break;
    }
}
void heapsort(int* a, int n) {
    int i;
    for (i = n / 2 - 1; i >= 0; i--)
        heapadjust(a, n, i);
    for (i = n - 1; i > 0; --i) {
        
         int t;
            t = a[0];
            a[0] = a[i];
            a[i]= t;
        heapadjust(a, i, 0);
    }
}
int main() {
    int n, i, a[1000];
    printf("输入排序个数，小于1000，然后回车\n");
    scanf("%d", &n);
    printf("随机产生\n");
    for (i = 0; i < n; ++i)
        a[i] = rand() % 400 + 200;
    for (i = 0; i < n; ++i)
        printf("%d ", a[i]);
    printf("输出\n");
    heapsort(a, n);
    for (i = 0; i < n; ++i)
        printf("%d ", a[i]);
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include<iostream>
#include<vector>
using namespace std;

int randInt(int min, int max)
{
    return rand() % (max - min + 1) + min;
}

void adjustHeap(vector<int>& arr, int start, int end) {
    int father = start;
    int child = 2 * father + 1;
    while (child < end) {
        if (child + 1 < end&&arr[child + 1] > arr[child]) {
            child++;
        }
        if (arr[father] < arr[child]) {
            swap(arr[father], arr[child]);
        }
        else {
            return;
        }
        father = child;
        child = 2 * father + 1;
    }
}
void HeapSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) {
        return;
    }
    for (int i = n / 2; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    while (n - 1) {
        swap(arr[0], arr[n - 1]);
        adjustHeap(arr, 0, n - 1);
        n--;
    }
}
void printArr(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "    ";
    }
    cout << endl;
}
int main() {
    srand((unsigned)time(NULL));// 产生随时间变化的随机数种子;
    int len = 250; // 令数组长度为250，为了符合题目生成200以上的随机整数;
    vector<int> arr;
    int randNum;
    for(int i = 0; i < len; i++)
    {
        randNum = randInt(0, 100);
        arr[i] = randNum;
    }
    HeapSort(arr);
    printArr(arr);
    return 0;
}

#include<stdio.h>
#include <time.h>
#define N 200
void swap(int num[],int i,int j)//交换结点
{
    int temp;
    temp=num[i];
    num[i]=num[j];
    num[j]=temp;
}
void Heapify(int num[],int len,int k)//最大堆调整
{
    if(k<len)
    {
        int max=k;//根结点
        int s1=2*k+1;//左子节点
        int s2=2*k+2;//右子结点
        //找出最大结点
        if(num[s1]>num[max]&&s1<len)
            max=s1;
        if(num[s2]>num[max]&&s2<len)
            max=s2;
        //交换最大子节点到根结点并做递归
        if(max!=k)
        {
            swap(num,max,k);
            Heapify(num,len,max);
        }
    }
}
void CreateHeap(int num[],int len)//创建最大堆
{
    int i;
    int last=len-1;                //最后一个子结点位置
    int parent=(last-1)/2;        //最后一个子结点的父结点
    for(i=parent;i>=0;i--)    
    {
        Heapify(num,len,i);        //从最后一个父结点开始做最大堆调整
    }
}
void HeapSort(int num[],int len)//堆排序
{
    int i;
    CreateHeap(num,len);        //创建最大堆

    for(i=len-1;i>=0;i--)    //依次将最大堆的根结点（最大值）取出
    {
        //将最大堆的根（最大值）换到最后
        swap(num,i,0);            
        //除去最大值,对交换后的二叉树做最大堆调整，使二叉树根结点始终为最大值    
        Heapify(num,i,0);        
    }
}
int main()
{
    int i;
    int num[N];
    srand((unsigned)time(NULL));
    for(i=0;i<N;i++)
    {
        num[i]=rand()%100;//100以内的整数 
    } 
    HeapSort(num,N);
    for(i=0;i<N;i++)
    {
        printf("%d",num[i]);
        printf("\n");
    }
    
    return 0;
}

排序原理
在堆的数据结构中，堆中的最大值总是位于根节点
其中堆定义了以下几种操作：
（一）最大堆调整（Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
（二）创建最大堆（CreateHeap）：将堆中的所有数据重新排序
（三）堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算