堆排序实现及应用

堆排序实现及应用

大家好,又见面了,我是全栈君。

        堆排序(Heapsort)是指利用堆这样的数据结构所设计的一种排序算法。

堆积是一个近似全然二叉树的结构。并同一时候满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

        堆排序实现及应用

一、堆的结构

       一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。

如第0个结点左右子结点下标分别为1和2。

这是从0開始的结构。

二、堆的分类

        堆分为最大堆(大顶堆)和最小堆(小顶堆),顾名思义就是父节点和左右孩子节点的关系,假设父节点大于全部的子节点的堆就是大顶堆,父节点小于全部子节点的堆就是小顶堆,选择大顶堆和小顶堆决定了排序的顺序,是从大到小还是从小到大排序。

三、堆的操作

1、创建及堆的插入

在堆中插入元素,事实上是一个上浮的操作,由于插入节点是在堆的最后,这个节点可能会破坏堆,所以须要通过调节这个插入元素的位置来终于恢复堆的有序性,这个操作就是一个上浮的操作。

堆排序实现及应用

上浮代码例如以下:
//k是插入元素的位置
void swim(int a[], int k)
{
    int j;
    while(k > 0)
    {
        j = (k - 1) / 2; //是k的父节点
        if(a[j] > a[k])
        {
           swap(&a[j], &a[k]);
           k = j;
        }
        else
        {
           break;
        }
    }
}


2、删除

依照定义删除仅仅能是删除第一个节点,也就是根节点,为了方便重建堆。所以须要将最后一个节点替换到根节点。然后又一次整理堆,这时就须要下降(sink)操作,将根节点逐渐的向下交换,最后使堆达到定义的要求。
堆排序实现及应用

代码例如以下:
//n是节点总数。删除总是从根节点開始
void sink(int a[], int n, int i)
{
   int j;
   while((2 * i + 1) < n)
   {
       j = 2 * i + 1;
       if(j + 1 < n && a[j] > a[j+1]) j++;
       if(a[j] < a[i])
       {
           swap(&a[i], &a[j]);
           i = j;
       }
       else
       {
           break;
       }
   }
}

3、建堆

怎样将一个普通的数组建成一个堆呢,那就须要对当前堆中的非叶子节点进行sink操作。最后达到堆的要求
堆排序实现及应用

代码例如以下:
void build_heap(int a[], int n)
{
   int i;
   for(i = (n/2 -1); i >= 0; i--)
   {
       sink(a, n, i);
   }
}

四、堆排序

回到正题。堆排序事实上就是不断的交换根节点和最后节点的过程。不断的缩小未排序集合的过程,这当中使用的就是sink操作
void heap_sort(int a[], int n)
{
   int i;
   for(i = n - 1; i > 0; i--)
   {
      swap(&a[i], &a[0]);
      sink(a, i, 0);
   }
}

最后将总体做了一个測试,代码例如以下:

#include <stdio.h>void swap(int *a, int *b){    int tmp = *a;    *a = *b;    *b = tmp;}//k是插入元素的位置void swim(int a[], int k){    int j;    while(k > 0)    {        j = (k - 1) / 2; //是k的父节点        if(a[j] > a[k])        {           swap(&a[j], &a[k]);           k = j;        }        else        {           break;        }    }}//n是节点总数。删除总是从根节点開始void sink(int a[], int n, int i){   int j;   while((2 * i + 1) < n)   {       j = 2 * i + 1;       if(j + 1 < n && a[j] > a[j+1]) j++;       if(a[j] < a[i])       {           swap(&a[i], &a[j]);           i = j;       }       else       {           break;       }   }}void build_heap(int a[], int n){   int i;   for(i = (n/2 -1); i >= 0; i--)   {       sink(a, n, i);   }}void heap_sort(int a[], int n){   int i;   for(i = n - 1; i > 0; i--)   {      swap(&a[i], &a[0]);      sink(a, i, 0);   }}int main(){    int a[4] = {10, 40, 30, 5};    swim(a, 3);    int i;    for(i = 0; i < 4; i++){       printf("%d\t", a[i]);    }    printf("\n");    int b[4] = {50, 10, 20, 40};    sink(b, 4, 0);    for(i = 0; i < 4; i++){       printf("%d\t", b[i]);    }    printf("\n");    int c[10] = {9, 12, 17, 30, 50, 20, 60 , 65, 4, 19};    build_heap(c, 10);    for(i = 0; i < 10; i++){       printf("%d\t", c[i]);    }    printf("\n");    heap_sort(c, 10);    for(i = 0; i < 10; i++){       printf("%d\t", c[i]);    }    printf("\n");}


堆排序实现及应用

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115277.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号