【C语言】堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
升序：建大堆
降序：建小堆

原因分析：

若升序建小堆时间复杂度是O(N^2)

升序建大堆，时间复杂度O（N*logN）

所以升序建大堆，降序建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

代码实现

#include<stdio.h>//交换函数
void Swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] = { 0,4,3,6,7,8,1 };HeapSort(a, sizeof(a) / sizeof(int));return 0;
}

运行结果

若是建小堆则只需要把向下调整中的>改成<,修改后如下

if (child + 1 < n && a[child + 1] < a[child])
{child++;
}
if (a[child] < a[parent])
{Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;
}

运行结果

当然我们也可以先写一个堆的数据结构再进行堆排序，但是这显然不如上面的快速且节省空间

自主实现数据结构堆再进行堆排序

代码实现

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//初始化
void HPArrayInit(HP* hp, HPDataType* a, int n);
//销毁
void HPDestroy(HP* hp);
// 堆的插入
void HPPush(HP* hp, HPDataType x);
// 堆的删除
void HPPop(HP* hp);
// 取堆顶的数据
HPDataType HPTop(HP* hp);
// 堆的数据个数
int HPSize(HP* hp);
// 堆的判空
int HPEmpty(HP* hp);
//向上调整算法
void Adjustup(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);void HPArrayInit(HP* hp, HPDataType* a, int n)
{assert(hp);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->a == NULL){perror("malloc fail");return;}memcpy(hp->a, a, n * sizeof(HPDataType));hp->size = hp->capacity = n;//向上调整,建堆时间复杂度O(N*logN)for (int i = 1; i < hp->size; i++){Adjustup(hp->a, i);}//向下调整，建堆时间复杂度O(N)for (int i = (hp->size - 1 - 1) / 2; i >= 0; i--){AdjustDown(hp->a, hp->size, i);}
}
//销毁
void HPDestroy(HP* hp)
{assert(hp);hp->size = hp->capacity = 0;free(hp->a);hp->a = NULL;
}
//交换函数
void Swap(HPDataType* px, HPDataType* py)
{HPDataType tmp;tmp = *px;*px = *py;*py = tmp;
}
//向上调整算法
void Adjustup(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;//找原本父亲的父亲下标}else{break;}}
}
// 堆的插入
void HPPush(HP* hp, HPDataType x)
{assert(hp);//扩容if (hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}hp->a = tmp;hp->capacity = newcapacity;}hp->a[hp->size++] = x;Adjustup(hp->a, hp->size - 1);
}
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}
// 堆的删除
void HPPop(HP* hp)
{assert(hp);assert(hp->size > 0);Swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HPTop(HP* hp)
{assert(hp);return hp->a[0];
}
// 堆的数据个数
int HPSize(HP* hp)
{assert(hp);return hp->size;
}
// 堆的判空
int HPEmpty(HP* hp)
{assert(hp);return hp->size == 0;
}
void HeapSort(int* a, int n)
{HP hp;HPArrayInit(&hp, a, n);int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);//将堆顶数据放入数组中HPPop(&hp);//再已放入数组中的堆顶数据删除}HPDestroy(&hp);
}
int main()
{int a[] = { 60,70,65,50,32,100 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++){printf("%d ", a[i]);}return 0;
}

运行结果

欢迎各位大佬一起学习交流~