C语言模拟实现堆排序
堆排序是一种效率比较高的排序方法，时间复杂度。
堆分为大堆和小堆，如果想要拍升序我们需要建立大堆，而如果想要拍降序则需要建立小堆，在使用堆排序前需要先建立一个堆，如果不会建立可以看我前面写的C语言模拟实现堆的代码。
堆是一个完全二叉树，因此一个数组就是一个完全二叉树。
一、堆的建立
我们可以先写一个图中的数组
，然后将其变成一个堆。运行代码如下：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a; //用来表示堆的数组
int capacity;
int size;
}Heap;
void Test01()
{
Heap hp;
HeapInit(&hp); //初始化一个堆
int arr[] = { 8,5,3,4,8,21,5,4,68,24 };
int i = 0;
int sz = sizeof(arr) / sizeof(int);
for (i = 0; i < sz; i++)
{
HeapPush(&hp, arr[i]); //将数组arr中的元素一个个插入到堆中的数组中
然后构建成一个堆
}
for (i = 0; i < sz; i++)
{
arr[i] = hp.a[i];//再将堆中的元素重新把数组的元素覆盖，
arr数组中的元素便构成堆
}
HeapDestory(&hp);
}代码运行后的结果如图 
，在逻辑结构上的表示如图：
我们可以清楚的看到这是一个小堆。
上述的方法可行，但过于麻烦。
1.向上调整算法构建堆
我们可以直接在原数组arr中使用向上调整算法构建堆。向上调整算法的代码如下 ：
void AdjustUp(HPDataType* a, int child) //构建小堆
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent]) //如果孩子小于父亲，内容就互换
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}在没有排序前，数组arr的逻辑结构如图：
，在这里我们要构建的是小堆，因此父结点的值小于等于子结点的值。向上调整我们要从上往下看，先看第一个节点8，忽略掉其他的节点，由于只有一个节点，因此它自己构成一个堆。然后看第一个节点和第二个节点，第二个节点5小于8，因此向上调整，数字5和8的位置互换，如图
再看第一个节点和第三个节点，数字5大于数字3，因此3和5的位置需要互换，如图：
这样前三个节点变构成一个小堆，然后依次往下构建，直到结束。在这里我们只需要比较父结点和子结点的大小，兄弟结点之间没有要求。我们可以看到一个节点就是一个小堆，因此我们只需要从第二个结点开始比较。
由于在物理结构上是一个数组，因此父结点与子结点之间的关系是：parent = (child - 1) / 2、
leftchild = parent * 2 + 1、 rightchild = parent * 2 + 2
代码实现如图：
void Test01()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 8,5,3,4,8,21,5,4,68,24 };
int i = 0;
int sz = sizeof(arr) / sizeof(int);
for (i = 1; i < sz; i++)
{
AdjustUp(arr, i);
}
HeapDestory(&hp);
}
代码运行后结果如图：
，我们可以看出这也是个小堆。
2.向下调整算法构建堆
向下调整算法如下：
void AdjustDown(HPDataType* a, int n, int parent) //n是数组的大小
{
assert(a);
int child = parent * 2 + 1; // 假设左孩子小于右孩子
while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1]) //child+1 < n保证右孩子存在
{
child++;
} //运行到此处，变量child存储的是最小孩子的位置
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}向下调整算法，我们要从下往上看，如图
由于21,5,4,68,24这些结点没有孩子，因此不需要向下调整，故向下调整算法我们要从最后一个节点的父结点（即非叶子结点的最后一个）开始向下调。由于在数组上有n个空间，因此最后一个结点的位置为n-1，故它的父结点的位置是(n-1-1)/2，故我们要从结点24的父结点8开始向下调。由于结点24大于结点8，因此8不需要向下调整。然后看结点4，结点4的孩子分别是4和68，由于两个孩子中，结点4要小于68，且与父结点相等，因此父结点4也不需要向下调整。依次向上遍历，直到结束。代码如下：
void Test01()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 8,5,3,4,8,21,5,4,68,24 };
int i = 0;
int sz = sizeof(arr) / sizeof(int);
for (i = (sz - 2) / 2; i >= 0; --i)
{
AdjustDown(arr, sz, i);
}
HeapDestory(&hp);
}运行结果如图
，我们可以得到一个小堆。
注：运行结果不唯一
二、排序的实现
由于在上述代码中，我们构建的是一个小堆，因此我们要排降序。
上面构建的小堆如图：
我们排降序的方法是首先把根结点和最后一个结点的位置互换，其次忽略掉最后一个节点（即最小的数字），最后将互换后的根结点向下调整重新构建成堆，重复上述操作便可以排成降序。
小堆的数组形式如图：
运行代码：
void Test01()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 8,5,3,4,8,21,5,4,68,24 };
int i = 0;
int sz = sizeof(arr) / sizeof(int);
for (i = (sz - 2) / 2; i >= 0; --i)
{
AdjustDown(arr, sz, i);
}
int end = sz - 1;//最后一个元素的位置
while (end > 0)
{
Swap(&arr[0], &arr[end]);
end--;
AdjustDown(arr, end, 0);
}
HeapDestory(&hp);
}运行结构如图 ：
这样便实现堆排序
原文地址：https://blog.csdn.net/N_N12/article/details/143455362
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！