ホームページ  >  記事  >  php教程  >  经典算法学习堆排序

经典算法学习堆排序

WBOY
WBOYオリジナル
2016-06-13 08:41:311530ブラウズ

经典算法学习——堆排序

堆排序是相对其他排序稍微麻烦的排序,是一种利用堆的性质进行的选择排序。堆其实是一棵完全二叉树,只要任何一个非叶节点的关键字不大于或者不小于其左右孩子节点,就可以形成堆。堆分为大顶堆和小顶堆。由上述性质可知大顶堆的堆顶的关键字是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。堆排序同快速排序一样都是不稳定排序。示例代码上传至:https://github.com/chenyufeng1991/HeapSort

堆排序的思想:利用大顶堆(小顶堆) 堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。注意:大顶堆构造的是递增序列,小顶堆构造的是递减序列。

(1)将初始待排序关键字序列(R0,R1....Rn-1),构建成大顶堆,此堆为初始的无序区;

(2)将堆顶元素R[0]与最后一个元素R[n-1]交换,此时得到新的无序区(R0,R1....Rn-2)和新的有序区(Rn-1),且满足R[0,1...n-2]

(3)由于交换后新的堆顶R[0]可能违反堆的性质,因此需要对当前无序区(R0,R1...Rn-2)调整为新堆,然后再次将R[0]与无序区最后一个元素交换,得到新的无序区(R0,R1...Rn-3)和新的有序区(Rn-2,Rn-1).不断重复此过程知道有序区的元素个数为n-1,则整个排序过程完成。

 

操作过程如下:

(1)初始化堆:将[0...n-1]构造为堆;

(2)将当前无序区的堆顶元素R[0]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆;

因此对于堆排序,最重要的两个操作就是构造初始堆和调整堆,其实构造初始堆也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整。

实例代码如下:

//
//  main.c
//  Train
//
//  Created by chenyufeng on 16/1/30.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include <stdio.h>

void BuildHeap(int *a,int size);
void swap(int *a,int *b);
void HeapSort(int *a,int size);
void HeapAdjust(int *a,int i,int size);

int main(int argc,const char *argv[]){

    int a[] = {3,25,9,30,2};
    HeapSort(a, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ",a[i]);
    }

    return 0;
}

//建立堆
void BuildHeap(int *a,int size){

    for (int i = size - 1; i >= 0; i--) {
        HeapAdjust(a, i, size);
    }

}

//交换两个数
void swap(int *a,int *b){

    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//堆排序
void HeapSort(int *a,int size){

    BuildHeap(a, size);
    for (int i = size - 1; i >= 0; i--) {
        //交换堆顶和最后一个元素,即每次将剩余元素中的最大者放到后面;
        swap(&a[0], &a[i+1]);
        //重新调整堆为大顶堆;
        HeapAdjust(a, 0, i );
    }
}

//调整堆
void HeapAdjust(int *a,int i,int size){

    int lchild = 2 * i;//左孩子节点;
    int rchild = 2 * i + 1;//右孩子节点;
    int max = i;

    if (i <= size) {
        if (lchild <= size && a[lchild] > a[max]) {
            max = lchild;
        }

        if (rchild <= size && a[rchild] > a[max]) {
            max = rchild;
        }

        if (i != max) {
            swap(&a[i], &a[max]);
            //避免调整之后以max为父节点的子树不是堆;
            HeapAdjust(a, max, size);
        }
    }
}</stdio.h>
声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。