常用的排序算法属快速排序和堆排序应用的最多，快速排序的递归版本要受限制于栈空间溢出问题的困扰，无法处理大量数据排序（但是对于外存上的数据进行排序，什么排序算法猜算是适合的？也许mergeSort会是一种选择，但是这个要再考虑）。而其他的排序包括插入排序，归并排序，冒泡排序，选择排序，相较于这两种排序算法，或者在时间或者空间上消耗要更大。

HeapSort算法是一个就地的排序算法，时间复杂度和quickSort一样，为O(N*LogN)，同时和快速排序一样，是不稳定的排序（貌似ShellSort，QuickSort，HeapSort这三种最高效的排序都是不稳定的，但是InsertSort，BubbleSort是稳定的）。并且在实现上，除了在保持堆结构的过程当中需要使用递归（由于是和深度有关的，所以递归的次数很少，而且应该是可以做尾递归优化的，是不是？），要了解堆排序首先要了解堆得定义。

Heap在计算机领域有两个主要的解释：

1.Heap是一种数据结构，在逻辑上为一颗完全二叉树，在物理上表现为一个数组。

2.Heap是一个程序执行空间当中的可动态申请的内存区域。

在堆排序当中，我们当然是选择第一种解释，堆的性质主要表现在如下的两个方面（以最大堆为例）：

1.堆的任何一个节点的都要大于它的后裔

2.堆是一颗完全二叉树

 

如果把堆看成一种数据结构，那么对于定义抽象数据类型来说，堆的常用操作包括：

1.HeapIdf():保持堆得性质

2.BuildHeap():建立初始堆

3.Insert():插入新的元素进入堆

4.Update()：更新堆元素的key并保持堆结构

5.get():获取堆顶部的元素

6.delete():删除堆顶部的元素并保持堆结构

 

但是对HeapSort来说，只有1,3是用到的，具体的HeapSort算法，我用C实现的版本如下：

#include 
     
      #include "heapsort.h"//data:heap data///size: the size of the heap//i: the node neeeded to be adjustedint parent(int i){        return (i-1)/2;}int left(int i){    return (i*2+1);}int right(int i){    return (i*2+2);    }void maxHeapIdf(int data[],int size,int i){    int largerId;    int temp;     int l,r;          l=left(i);     r=right(i);          largerId=i;    if(l
      
       =0;i--){        maxHeapIdf(data,size,i);    }    }void heapSort(int data[],int size){    int i;    int temp;        buildMaxHeap(data,size);        for(i=size-1;i>=0;i--){        temp=data[i];        data[i]=data[0];        data[0]=temp;        maxHeapIdf(data,i,0);    }}void print(int A[],int heap_size){    int i;    for(i = 0; i < heap_size;i++)    {        printf("%d ", A[i]);    }    printf("\n");}int main(){    int data[]={        5,2,3,7,6,4,1    };    heapSort(data,7);    print(data,7);}
      
     

 

Heap结构除了可以应用到排序上，还是作为优先级队列的一种选择，优先级队里可以用于比如进程调度等场合。