前言
一種將無序數(shù)組進行排序的方法。
堆排序，wiki參考：
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
堆排序，主要思想：將一維數(shù)組構(gòu)造成堆結(jié)構(gòu)咸产，再對堆結(jié)構(gòu)進行排序。
環(huán)境
編輯器：vs2019
文件：.c類型
正文
代碼參考：
#include <stdio.h>
// 父節(jié)點i的左子節(jié)點在位置 2i + 1 ;
// 父節(jié)點i的右子節(jié)點在位置 2i + 2 ;
// 堆排序， 類似于滿二叉樹琼掠。
// 1. 構(gòu)建大頂堆結(jié)構(gòu)
// 2. 通過大頂堆結(jié)構(gòu)排序
void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}
// 構(gòu)建大頂堆， 從小到大排序停撞，父節(jié)點大于子節(jié)點瓷蛙。
void _max_heap_sort(int source_array[], int start, int end)
{
// 父節(jié)點
int dad = start;
// 子節(jié)點中最大的節(jié)點，默認為左子節(jié)點戈毒。
int son = dad * 2 + 1;
while (son <= end)
{
// 找出子節(jié)點中最大的
if (son + 1 <= end && source_array[son + 1] > source_array[son])
{
// 如果右子節(jié)點大于左子節(jié)點艰猬，則son 指向右子節(jié)點
son++;
}
// 已經(jīng)找到最大的子節(jié)點，開始調(diào)整父節(jié)點與子節(jié)點滿足大頂堆埋市。
if (source_array[son] > source_array[dad])
{
swap(&source_array[son], &source_array[dad]);
}
dad = son;
son = dad * 2 + 1;
}
}
void max_heap_sort_normal(int source_array[], int source_array_length)
{
int i;
// 1. 構(gòu)造大頂堆結(jié)構(gòu)
// 遍歷每一個父節(jié)點冠桃。大頂堆要求父節(jié)點大于子節(jié)點，因此采用逆序的方式道宅。
for (i = source_array_length / 2 - 1; i >= 0; i--)
{
_max_heap_sort(source_array, i, source_array_length - 1);
}
// 2. 通過大頂堆結(jié)構(gòu)進行排序食听。
// 每次都讓列表的第一個值最大，然后將最大值移到最后污茵，有點選擇排序的意味樱报。
for (i = source_array_length - 1; i > 0; i--)
{
// 將最大值移到末尾
swap(&source_array[0], &source_array[i]);
// 將打亂的大頂堆，重新構(gòu)造省咨。
_max_heap_sort(source_array, 0, i - 1);
}
}
int main()
{
// 生成隨機測試列表
int test_list[20];
int test_list_length = sizeof(test_list) / sizeof(int);
printf("測試列表： \n");
for (int i = 0; i < test_list_length; i++)
{
test_list[i] = rand() % 100;
printf("%d ", test_list[i]);
}
printf("\n");
// 普通堆排序
max_heap_sort_normal(test_list, test_list_length);
printf("普通堆排序結(jié)果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
return 0;
}
執(zhí)行結(jié)果參考：
image.png
