基于数组的堆排序算法的C语言实现

2019-11-06 07:10:48

字体：大中小

来源：转载

供稿：网友

实现如下：

#include <stdio.h>#include <stdlib.h>#define SIZE 20#define DEBUG 1void PRintArray(int array[], const int size);void initArray(int array[], const int size);void swap(int *p1, int *p2);void heap_sort(int array[], const int size);int parent(int p);int left_child(int p);int right_child(int p);void max_heapify(int array[], const int size, int p);void build_max_heap(int array[], const int size);#ifdef DEBUGint testArray[SIZE];void saveTest(int array[], const int size) { int count = 0; for (count = 0; count < size; count++) { testArray[array[count]]++; }}int test(int array[], const int size) { int count = 0; for (count = 0; count < size; count++) { testArray[array[count]]--; } for (count = 0; count < size; count++) { if (testArray[count] != 0) return 0; } return 1;}#endifint main(int argc, char const *argv[]){ int array[SIZE]; initArray(array, SIZE);#ifdef DEBUG saveTest(array, SIZE);#endif printArray(array, SIZE); heap_sort(array, SIZE); printArray(array, SIZE);#ifdef DEBUG int result = test(array, SIZE); printf("The sorting result is %s/n", result ? "right" : "wrong");#endif return 0;}void printArray(int array[], const int size) { printf("The current array is:/n"); int count = 0; for (count = 0; count < size; count++) { printf("%d ", array[count]); } printf("/n");}void initArray(int array[], const int size) { int count = 0; srand(time(NULL)); for (count = 0; count < size; count++) { array[count] = rand() % size + 1; }}void swap(int *p1, int *p2) { int temp = *p1; *p1 = *p2; *p2 = temp;}int parent(int p) { return (p - 1) / 2;}int left_child(int p) { return 2 * p + 1;}int right_child(int p) { return 2 * p + 2;}void max_heapify(int array[], const int size, int p) { int max = p; if (left_child(p) < size && array[max] < array[left_child(p)]) { max = left_child(p); } if (right_child(p) < size && array[max] < array[right_child(p)]) { max = right_child(p); } if (max == p) return; swap(&array[max], &array[p]); max_heapify(array, size, max);}void build_max_heap(int array[], const int size) { int count = size / 2; for (; count >= 0; count--) { max_heapify(array, size, count); }}void heap_sort(int array[], const int size) { build_max_heap(array, size); int count = 1; for (count = 1; count < size; count++) { swap(&array[0], &array[size - count]); max_heapify(array, size - count, 0); }}

该程序使用标准函数库中函数rand随机产生SIZE个随机数并对其进行堆排序。堆排序是不稳定原地的排序。该程序中使用的数组作为表示堆的数据结构，其计算左子女，右子女以及父节点的坐标的方式如parent，left_child，right_child所示。 max_heapify使其保持最大堆的性质，假设p节点左右两颗子树都是最大堆，max_heapify使p节点保持最大堆的性质，选取p节点的左右子女中最大的与p节点交换，然后递归的对交换后的节点继续进行max_heapify操作，直到到达叶子结点。max_heapify操作运行时间的渐近上界为O(h) $Ο(h)$ h为待操作节点的高度。 build_max_heap将一个数组建立为最大堆，从最后一个非叶子节点到根节点依次分别调用max_heapify函数即可。其操作时间的渐近确界为O(n) $Ο(n)$ 。 heap_sort函数对n个数进行堆排序，每次将最大堆的第一个元素和最后一个元素交换，得到最大的元素，将堆的元素个数减一后再对堆的根节点进行max_heapify操作，得到当前堆中最大元素，循环n-1次即可排序数组。其操作时间的渐近确界为O(nlogn) $Ο(nlogn)$ 。其上所有算法复杂度计算方法见算法导论第六章，涉及主定理不再赘述。

上一篇：SpringMVC主要流程概述（学习笔记）

下一篇：237. Delete Node in a Linked List