堆排序详解:点这里。
使用向下调整算法实现堆排序,完整代码
#include<stdio.h>
void Swap(int* p1, int* p2)
{
int* tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Print(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 堆排序,建大堆
void AdjustDown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = 2 * parent + 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--;
}
}
void test()
{
int arr[] = { 6,3,4,2,0,1,8,7,5 };
int len = sizeof(arr) / sizeof(int);
HeapSort(arr, len);
Print(arr, len);
}
int main()
{
test();
return 0;
}