数据结构与算法|C/C++ 堆排序的非递归实现排序算法|数据结构|堆排序|c

C/C++ 数据结构堆排序的快速实现

本章所需知识点：
- 大根堆和小根堆的定义
- 如何编写非递归的堆排序

本章所需知识点： 1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
2.左孩子索引：2*i+1
3.右孩子索引：2*i+2
大根堆和小根堆的定义

大根堆和小根堆
性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。

如何编写非递归的堆排序堆排序原理参考文档
非递归堆排序流程图：
求最大根堆即是数组A的MAXSIZE-1 数组A排序区间为0->MAXSIZE 根结点和最后一个数交换数组A所需排序的最大值-1 下面展示非递归堆排序的 代码片

// A为存放着需要进行堆排序数据的数组 void heapSort(DateType A[],int size) { int i,j,temp; for (j = size-1; j >=0; j--) {//执行size-1次，每次将最大根堆的根节点与最后一个数交换 for (i = j; i >= 0; i--) {//从未排序成最大根堆的最后一个点往前排序 if (A[i] > A[(i - 1) / 2] && (i - 1) / 2 >= 0) {//如果比父级大，则与父级交换 temp = A[i]; A[i] = A[(i - 1) / 2]; A[(i - 1) / 2] = temp; } }temp = A[0]; A[0] = A[j]; A[j] = temp; //将最大根堆的根节点与最后一个数交换 //然后排序剩余的堆 } }

题目：

生成500个在[200, 10000]之间的整数保存数组A中，以此数组元素作为关键字，采用堆排序算法按非递减（递增）方式进行排序

【数据结构与算法|C/C++ 堆排序的非递归实现】rand函数参考文档

#include.h> #include.h> #include.h>//涵括了rand函数 #define maxsize 500typedef int DateType; void main() { int i=0,j,temp=0; int size; void heapSort(DateType A[],int size); //随机生成1000个数（因为随机数是会重复的，所以这里采取保存到B数组中，经过比较再保存到A数组中） DateType A[maxsize] = { -1 }, B[1000]; //数组初始化，全部赋值为-1 for (i = 0; i < 1000; i++) {//循环生成随机整数1000个 B[i] = rand() % 9800 + 200; //限定随机数的生成区间为200-10000 } //我的题目要求是生成五百个互不相同的随机数，所以直接将i的上限写成500 //其他需求的可以用scanf语句键入所需的数量 for (i = 0; i < 500; i++) {//将B数组中的随机数保存到A数组中 for (j = 0; j < i; j++) { while (B[temp] == A[j])temp++; } A[i] = B[temp]; temp++; } size=500; //数组访问下标的上限 heapSort(A,size); } void heapSort(DateType A[],int size) { int i,j,temp; for (j = size-1; j >=0; j--) {//执行size-1次，每次将最大根堆的根节点与最后一个数交换 for (i = j; i >= 0; i--) {//从未排序成最大根堆的最后一个点往前排序 if (A[i] > A[(i - 1) / 2] && (i - 1) / 2 >= 0) {//如果比父级大，则与父级交换 temp = A[i]; A[i] = A[(i - 1) / 2]; A[(i - 1) / 2] = temp; } }temp = A[0]; A[0] = A[j]; A[j] = temp; //将最大根堆的根节点与最后一个数交换 //然后排序剩余的堆 } }