欢迎来到军工软件开发人才培养基地——学到牛牛

十大排序——堆排序

时间:2024-05-06 07:01:10 来源:学到牛牛

今天要讲到的呢是十大排序中的堆排序,在介绍堆排序算法之前呢,我们得先知道堆是什么?

堆是一种非常灵活的数据结构,我们可以通过堆来解决一些问题,从它的本质上来说,堆就是二叉树的数据结构,这一点从图1-1可以明显看出

图1-1

堆排序算法中还分成大顶堆和小顶堆两种方法(图1-2所示):

图1-2

大顶堆:每个节点的值都大于或者等于其子节点的值,可理解为堆排序中的升序排序。

小顶堆:每个节点的值都小于或者等于其子节点的值,可理解为堆排序中的降序排序。

在大概了解了堆之后,我们再来看一看实现堆排序的基本思想:

堆一般存储于数组中,从头到尾按顺序扫描数组中的数,找到最小关键字或者最大关键字(按升序或降序进行选择,这里为升序排序只需找到最小关键字即可),找到最小关键字和数组中第一个数字进行交换,然后继续从无序序列中找到最小的关键字插入有序序列,每一次的排序都能找到最小的关键字,直到排序结束

详细步骤:

假设我们给出一个待排序数组A{20,12,15,17,9,8,16,10,22,6,11,7};

一:根据无序数组创建一个堆(升序采用大顶堆,降序采用小顶堆),我们现在的堆就是一个无规则的二叉树,将序列的值从上到下,从左到右的顺序依次对二叉树进行填充(如图1-1所示)

图1-1

二:接下来对堆进行调整,使其变成大顶堆,根据大顶堆的性质,每个节点的值都大于或者等于其子节点的值,所以要对节点和子节点进行比较,从而调整他们的父子关系,如果二叉树从上往下遍历比较的话,会存在节点进行交换,而他的子节点还没遍历到,比较的次数和交换的次数会增加,从而效率更低,所以我们选择从下往上进行遍历,一层一层依次进行,先遍历第一遍会发现17 < 22,需要调整他们的父子关系(如图1-2所示)

图1-2

9 < 11,需要调整他们的父子关系(如1-3所示)

 

图1-3

按照以上方法,最终调整堆为大顶堆,最上层节点数大于他的子节点(如图1-4所示)

 

图1-4

用数组进行存储,现在就可以得到一个大顶堆的存储结构(如图1-5所示)

图1-5

 

 

三:用堆排序进行排序

根据大顶堆的性质,当前堆的顶堆就是整个序列中最大的值,找到最大关键字(或最小关键字),把最大关键字和数组最后一个元素交换,把剩下的序列重新构造成最大堆(或最小堆),一直重复此操作,最后就能得到一个有序的数组。

具体步骤:

我们目前得到的大顶堆如图1-6所示:

图1-6

根据大顶堆的性质,当前堆的顶堆就是最大关键数,我们把最大关键数和序列最后一个数进行交换(如图1-7所示)

图1-7

交换完成之后,22这个数字为有序区,不用参与之后的比较,然后将剩余的元素重新构建大顶堆,其实就是调整根节点以及其调整后影响的子节点,因为其他节点之前已经满足大顶堆性质,第一轮排序结束如图1-8所示

图1-8

继续交换20与9 扩大有序区 ,剩下的序列再次重新构造大顶堆。

一直重复此操作,直到变成有序的序列(如图1-9所示)

图1-9

详细代码:

#include <stdio.h>

#include <stdlib.h>

 

void swap(int* a, int* b) {

    int temp = *b;

    *b = *a;

*a = temp;

}

void max_heapify(int arr[], int start, int end) {

    //建立父节点指标和子节点指标    int dad = start;

    int son = dad * 2 + 1;

while (son <= end) { //若子节点指标在范围内才做比较      

if (son + 1 <= end && arr[son] < arr[son + 1]) 

//先比较两个子节点大小,选择最大的           

son++;

        if (arr[dad] > arr[son]) 

//如果父节点大于子节点代表调整完毕,直接跳出函数            

return;

        else { 

//否则交换父子内容再继续子节点和孙节点比较            s

wap(&arr[dad], &arr[son]);

            dad = son;

            son = dad * 2 + 1;

        }

}}

void heap_sort(int arr[], int len) 

{

    int i;

//初始化,i从最后一个父节点开始调整    

for (i = len / 2 - 1; i >= 0; i--)

        max_heapify(arr, i, len - 1);

//先将第一个元素和已排好元素前一位做交换,再从新调整,直到排序完毕    

for (i = len - 1; i > 0; i--)

{

        swap(&arr[0], &arr[i]);

        max_heapify(arr, 0, i - 1);

}

}

int main() 

{

    int arr[] = { 20,12,15,17,9,8,16,10,22,6,11,7 };

    int len = (int) sizeof(arr) / sizeof(*arr);

    heap_sort(arr, len);

    int i;

    for (i = 0; i < len; i++)

        printf("%d ", arr[i]);

    printf("\n");

    return 0;

}