排序算法–堆排序
堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。
二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：
堆的存储
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2。如第0个结点左右子结点下标分别为1和2。
对一个给定的数组排序，虚拟主机，主要分为两个步骤：建立堆，进行排序。在建堆和排序的过程中，虚拟主机，香港空间，堆的维护都是最重要的步骤。
建立小根堆：
堆排序：
代码：
#include <stdio.h>#include <stdlib.h>void swap(int root,int min,int sque[]){int tmp;tmp = sque[root];sque[root] = sque[min];sque[min] = tmp;}void PercolateDown(int sque[], int root, int size){int left = root*2+1;int right = root*2+2;int min = 0;int i = 0;while(left < size-1){min = left;(right <= size-1)// if right child exists{if(sque[left] > sque[right])min = right;}if(sque[root]<sque[min])break;if(sque[root]>sque[min]){swap(root,min,sque);root = min;left = root*2+1;right = root*2+2;}}}void buildHeap(int sque[], int size){int i=0;for(i=size/2;i>=0;i–){PercolateDown(sque,i,size);}}void HeapSort(int sque[],int size){int i=0;for(i=9;i>=1;i–){swap(0,i,sque);size–;PercolateDown(sque,0,size);}}int main(){sque[10]={1,2,3,4,5,6,7,8,9,10};int size = 10;int i=0;buildHeap(sque,size);for(;i<=9;i++)printf(,sque[i]);printf();printf();printf();HeapSort(sque,size);for(i=0;i<=9;i++)printf(,sque[i]);printf();system();return 0;}
posted on
一切都在发展变化，不断地向昨天告别，满怀信心地投入每一个崭新的今天。
