八大排序算法——堆排序
目录
前言
一、向上调整算法建堆
二、向下调整算法建堆
三、堆排序
前言
堆排序是基于堆结构的一种排序思想，因此要为一个乱序的数组进行排序的前提是数组必须要是一个堆，所以要先对数组进行建堆操作
一、向上调整算法建堆
时间复杂度：O（ n*logn ）
由于向上调整算法建堆的时间复杂度的证明太过晦涩难懂，还要涉及数学中的错位相减法，所以这里就不证明了，感兴趣的可以自己去了解一下
这里只需要知道向上调整算法建堆的时间复杂度为 O（ n*logn ）
//交换两个数的位置
void sweap(int* num1, int* num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//向上调整算法（大根堆）
void AdjustUp(int* arr, int pos)
{
//当前调整的位置不能是堆顶
if (pos == 0)
{
return;
}
//寻找双亲节点
int parents = (pos - 1) / 2;
//当前位置与双亲节点进行比较
//如果当前位置的数大于双亲节点，就进行交换，并且继续向上调整
//如果当前位置的数小于双亲节点，表示堆已经构建好了
if (arr[parents] < arr[pos])
{
//交换两个数位置
sweap(&arr[parents], &arr[pos]);
//继续向上调整
AdjustUp(arr, parents);
}
}
int main()
{
//给定一个乱序数组
int arr[] = { 8,3,2,6,7,1,4,9,5 };
//计算数组元素个数
int size = sizeof(arr) / sizeof(arr[0]);
//向上调整算法建堆
//从前往后依次调整建堆
//先让节点之前的数为堆，然后整体为堆
for (int i = 0; i < size; i++)
{
AdjustUp(arr, i);
}
return 0;
}
二、向下调整算法建堆
时间复杂度：O（ n ）
由于向下调整算法建堆的时间复杂度的证明太过晦涩难懂，还要涉及数学中的错位相减法，所以这里就不证明了，感兴趣的可以自己去了解一下
这里只需要知道向下调整算法建堆的时间复杂度为 O（ n ）
//交换两个数的位置
void sweap(int* num1, int* num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//向下调整算法（大根堆）
void AdjustDown(int* arr, int size, int pos)
{
//左孩子位置
int child = pos * 2 + 1;
//向下调整算法，直到左孩子位置大于数组个数
if (child < size)
{
//选出左右孩子中最大的那个孩子
if (child + 1 < size && arr[child] < arr[child + 1])
{
child++;
}
//与当前位置进行比较
//如果左右孩子中最大数大于当前位置的数，就进行交换，并且继续向下调整
//如果左右孩子中最大数小于当前位置的数，表示堆已经调整好了
if (arr[child] > arr[pos])
{
//交换两个数的位置
sweap(&arr[pos], &arr[child]);
//继续向下调整
AdjustDown(arr, size, child);
}
}
}
int main()
{
//给定一个乱序数组
int arr[] = { 8,3,2,6,7,1,4,9,5 };
//计算数组元素个数
int size = sizeof(arr) / sizeof(arr[0]);
//向上调整算法建堆
//从最后一个叶子节点父节点往前依次调整建堆
//先让节点的左右子树为堆，然后整体为堆
int pos = (size - 1) / 2;//最后一个叶子节点父节点
for (int i = pos; i >= 0; i--)
{
AdjustDown(arr, size, i);
}
return 0;
}
三、堆排序
时间复杂度：O（ n*logn ）
在进行建堆操作时我们可以选择向上调整算法和向下调整算法，但是由于向下调整算法的时间复杂度要优于向上调整算法，因此更推荐使用向下调整算法建堆
建堆的时间复杂度为O（ n ），每次调整的堆结构的时间复杂度为O（ logn ） ，因此整体时间复杂度为O（ n*logn ）
堆排序的过程大致如下：
- 将待排序的数组构造成一个大顶堆（或小顶堆，根据需要）。此时，整个数组的最大值（或最小值）就是堆结构的顶端
- 将顶端的数与末尾的数交换。此时，末尾的数为最大值（或最小值），剩余待排序数组个数为n-1
- 将剩余的n-1个数再构造成大顶堆（或小顶堆），再将顶端数与n-1位置的数交换。如此反复执行，便能得到有序数组
【注意】
- 排升序要建大堆
- 排降序要建小堆
整体代码实现
//交换两个数的位置
void sweap(int* num1, int* num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//向下调整算法（大根堆）
void AdjustDown(int* arr, int size, int pos)
{
//左孩子位置
int child = pos * 2 + 1;
//向下调整算法，直到左孩子位置大于数组个数
if (child < size)
{
//选出左右孩子中最大的那个孩子
if (child + 1 < size && arr[child] < arr[child + 1])
{
child++;
}
//与当前位置进行比较
//如果左右孩子中最大数大于当前位置的数，就进行交换，并且继续向下调整
//如果左右孩子中最大数小于当前位置的数，表示堆已经调整好了
if (arr[child] > arr[pos])
{
//交换两个数的位置
sweap(&arr[pos], &arr[child]);
//继续向下调整
AdjustDown(arr, size, child);
}
}
}
//堆排序——升序
void HeapSort(int* arr, int size)
{
//从后往前依次调整建堆
//先让节点的左右子树为堆，然后整体为堆
int pos = (size - 1) / 2;//最后一个叶子节点父节点
for (int i = pos; i >= 0; i--)
{
//向下调整建堆
AdjustDown(arr, size, i);
}
//堆排序
//排升序要建大堆
//排降序要建小堆
for (int i = 0; i < size; i++)
{
//堆顶与最后一个有效元素交换位置
sweap(&arr[0], &arr[size - 1 - i]);
//向下调整，保持堆的结构
AdjustDown(arr, size - i - 1, 0);
}
}
int main()
{
//给定一个乱序数组
int arr[] = { 8,3,2,6,7,1,4,9,5 };
//计算数组元素个数
int size = sizeof(arr) / sizeof(arr[0]);
//堆排序
HeapSort(arr, size);
//打印排序后的数据
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
return 0;
} 