c语言中如何实现堆排序

这篇文章给大家介绍c语言中如何实现堆排序，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;

如上图所示，序列R{3, 5, 8, 10, 7}是一个典型的小根堆。
堆中有两个父结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素5在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2i+1];
(2) 它的右孩子结点是：R[2i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2i+1] 且 R[i] <= R[2i+2]。
首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。
以上思想可归纳为两个操作：
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
先通过详细的实例图来看一下，如何构建初始堆。
设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后，我们来看一下完整的堆排序处理：
还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。
代码：

#include #include void    HeapAdjust(int *array, int parent, int length);void    printPart(int *array, int begin, int end);int main(){    int array[10] = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};    int length = (sizeof(array) / sizeof(int));    for (int i = length / 2 ; i >= 0; i--)    {        HeapAdjust(array, i, length);    }    for (int i = length - 1; i > 0; i--)     {        // 最后一个元素和第一元素进行交换        int temp = array[i];        array[i] = array[0];        array[0] = temp;        // 筛选 array[0] 结点，得到i-1个结点的堆        HeapAdjust(array, 0, i);        printf("第 %d 趟: \t", length - i);        printPart(array, 0, length - 1);    }    system("pause");    return 0;}void    HeapAdjust(int *array, int parent, int length){    int tmp = array[parent];    int Lchild = 2 * parent + 1;    while (Lchild= array[Lchild])            break;        // 把孩子结点的值赋给父结点        array[parent] = array[Lchild];        // 选取孩子结点的左孩子结点,继续向下筛选        parent = Lchild;        Lchild = 2 * Lchild + 1;    }    array[parent] = tmp;}void printPart(int *array, int begin, int end){    for (int i = begin; i <= end; i++)     {        printf("%d \t",array[i]);    }    printf("\n");}

关于c语言中如何实现堆排序就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。