基于Linux操作系统下的堆排序算法-EW帮帮网

一、堆排序算法原理

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

（1）关于堆的相关概念

堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树

1. 堆的性质

① 是一棵完全二叉树
② 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。

2. 堆的存储

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)

3. 堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

① 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
② 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
③ 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

（2）堆排序的实现

1. 基本思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

2. 实现逻辑

① 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
② 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
④ 直到无序区只有一个元素为止。

3.实现过程图示

初始传入数据{62，41，30，28，16，22，13，19，17，15}，将其用大顶堆表示如下：

进行堆排序（大顶堆调整）：

排序完成后，结果如下：

二、代码实操

（1）heapsort.h

#ifndef _HEAPSORT_H
#define _HEAPSORT_H

#define MAXSIZE 10

typedef int data_t;
struct Max_Heap{
    data_t max;
    data_t lchild;
    data_t rchild;
}heap;
data_t data[MAXSIZE];

void swap(data_t *_src,data_t *_dest);
void MaxHeapify(data_t *data,int len,int i);
void Heap_Sort(data_t *data,int len);
void Heap_Show(data_t *data,int len);
#endif

（2）heapsort.c

#include <stdio.h>
//#include <strings.h>
#include <stdlib.h>
#include <string.h>
//#include <unistd.h>
#include "heapsort.h"

#define DEBUG 1

void swap(data_t *_src,data_t *_dest)    //交换函数
{
    data_t temp=*_src;
    *_src=*_dest;
    *_dest=temp;
}

void MaxHeapify(data_t *data,int len,int i)    //大顶堆调整函数
{
    int Max=i;
    int lift=2*i+1;
    int right=2*i+2;

    heap.max=data[Max];
    heap.lchild=data[lift];
    heap.rchild=data[right];
    if(lift<len && heap.max<heap.lchild && heap.rchild<heap.lchild)
        Max=lift;
    else if(right<len && heap.max<heap.rchild && heap.lchild<heap.rchild)
        Max=right;

    if(Max!=i){
        swap(&data[Max],&data[i]);
        MaxHeapify(data,len,Max);
    }
}

void Heap_Sort(data_t *data,int len)    //堆排序函数
{
    int i;
    for(i=len/2-1;i>=0;i--)
        MaxHeapify(data,len,i);
    for(i=len-1;i>1;i--){
        swap(&data[i],&data[0]);
        MaxHeapify(data,i,0);
    }
}

void Heap_Show(data_t *data,int len)    //堆显示函数
{
    int i=0;
    while(i<len){
        printf("%3d ",data[i]);
        i++;
    }
    printf("\n");
}

（3）main.c

#include <stdio.h>
//#include <strings.h>
#include <stdlib.h>
#include <string.h>
//#include <unistd.h>
#include <time.h>
#include "heapsort.h"

#define DEBUG 1

int main(int argc, char *argv[])
{ 
#if 1    //（#if 0）选择传入指定数据（随机数据）
    //int arr[]={62,41,30,28,16,22,13,19,17,15};
    int arr[]={100,5,3,11,33,6,8,7};
    int len=sizeof(arr)/sizeof(int);
    Heap_Show(arr,len);
    printf("**************************\n");
#else
    srand(time(0));
    int i=0;
    while(i<MAXSIZE){
        data[i]=rand()%100;
        i++;
    }
    Heap_Show(data,MAXSIZE);
    printf("**************************\n");
#endif
    printf("after Heap sort:\n");

#if 1    //（#if 0）根据传入数据选择排序与显示
    Heap_Sort(arr,len);
    Heap_Show(arr,len);
#else
    Heap_Sort(data,MAXSIZE);
    Heap_Show(data,MAXSIZE);
#endif

    return 0;
}

传入指定数据：

    //int arr[]={62,41,30,28,16,22,13,19,17,15};
    int arr[]={100,5,3,11,33,6,8,7};
    int len=sizeof(arr)/sizeof(int);
    Heap_Show(arr,len);
    printf("**************************\n");

传入随机数据：

    srand(time(0));
    int i=0;
    while(i<MAXSIZE){
        data[i]=rand()%100;
        i++;
    }
    Heap_Show(data,MAXSIZE);
    printf("**************************\n");

显示结果：

（指定数据）

（随机数据）

基于Linux操作系统下的堆排序算法