堆排序的实现

堆排序是利用了一种数据结构叫做二叉堆，二叉堆是这样定义的：

二叉堆是一种特殊的堆，二叉堆是完全二元树或者是近似完全二元树，有最小堆和最大堆

特点：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

利用堆排序数据的存储方式如下：

以下是我的代码实现：

void min_heap_shift(int a[], int i, int n){    int j = 2*i+1, temp;//非递归的实现    temp = a[i];    while(j < n)    {        if(a[j+1] < a[j] && j+1 < n)            j = 2*i+2;        if(temp < a[j])  break;        a[i] = a[j];        i = j;        j = 2*i+1;    }    a[i] = temp;}

如果在面试中需要我们去写堆排序，就记住两点三函数：

1.堆化一个数组 min_heapsize

2.堆排序 min_heap_sort

其中每次发生交换数据的时候我们读需要保持堆的特性，即min_heap_shift 函数

自己曾经写过的错的地方：

1.while(j < n)写成了while(j +1 < n)，这个以为左右孩子必须都小于ｎ，其实错了，右孩子可以没有
2.把最后的a[i] = temp写成了a[j] = temp;
这个地方用a[i]有以下几层含义：
当ｊ> n时，就是第一次没有交换的时候，a[i] == temp;
当发生了交换，a[i] = a[j]; i = j;此时a[j]的值被赋予了a[i],而ｊ = 2*i+1; 我们赋予a[j] = temp是错的，赋予a[i] = temp才是对的

另外堆排序和快速排序，归并排序的复杂度一样都是O(N*logN)，具体怎么来的，可以去看《算法导论》