排序算法之-堆排序
堆排序是利用堆的数据结构而设计的一种排序算法。堆是一种完全二叉树,它具有以下性质:即每个节点的值总是大于(或小于)它的父结点的值。
我们会用到两种堆:
大顶堆:每个节点都大于或等于它的子节点的值,称为大顶堆。
小顶堆:每个节点都小于或等于它的子节点的值,称为小顶堆。
每个列表都可以按下标顺序表示为一个二叉树,如下图:
算法步骤
- 构造初始堆(升序用大顶堆,降序用小顶堆)。
- 将堆顶元素与列表末尾元素交换,此时列表末尾元素为最大(或最小)。
- 将堆长度缩小 1,然后调整整个堆,使其满足堆的性质。
- 重复步骤 2, 3, 直到堆长度为1。
动图演示
代码示例
#define SORT_OK (0)
#define SORT_ERR (-1)
static void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
static void heapAdjust(int* array, int rootIndex, int end)
{
int value = array[rootIndex];
int child;
while ((child = rootIndex * 2 + 1) <= end)
{
if (child + 1 <= end && array[child + 1] > array[child])
child = child + 1;
if (array[rootIndex] < array[child])
{
swap(&array[rootIndex], &array[child]);
rootIndex = child;
}
else
break;
}
}
static void buildMaxHeap(int* array, int length)
{
for (int i = length / 2 - 1; i >= 0; i--)
{
heapAdjust(array, i, length - 1);
}
}
int heapSort(int* array, int arrLen)
{
if (array == NULL || arrLen < 0)
return SORT_ERR;
buildMaxHeap(array, arrLen);
for (int i = arrLen - 1; i >= 0; i--)
{
swap(&array[0], &array[i]);
heapAdjust(array, 0, i - 1);
}
}