算法导论 堆排序（不理解，请留下评论，必回）

原址排序；开辟少量的空间，用于周转存放临时数据，

堆排序不开辟新的空间，空间复杂度O（0）；是原址排序

时间复杂度O（n*logn），每一次（n）拿出堆顶元素后，堆的堆顶就会发生化，新的堆顶会在每次维护的时候不断比较下沉一次，下沉到底部是log（n）次，、元素是来自于底部，自然每个元素都会下沉到底，所以其时间是固定的，是n*log n；

相对于快速排序，建堆过程会打乱数据原有的相对先后顺序，导致数据的有序度降低， 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

但是堆排序也有其独到之处，比如优先队列的问题，当数组增加一个元素后，仅需要维护一次堆，便能达到要求，输出最值，而快速排序，需要将数组重排一次。

以下为c源码。

--------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 1000//数组元素的个数
void happen_rand(int* p, int n);//生成随机数
int heap(int* p,  int len);//堆排序
int set_up(int* p, int left, int right);//建立堆,并且维护最大堆
int main()
{
    int array[N];
    happen_rand(array, N);
    heap(array,  N - 1);
    for (int i = 0; i < N; i++) {//打印所有元素
        printf("%d\n",array[i]);
    }
    return 0;
}

void happen_rand(int* p, int n)
{
    srand(); 
    for (int i = 0; i < N; i++) {
        p[i] = rand() % N;

    }
}

int heap(int* p,  int len)
{
    int tmp;
    for (int i = 0; i < N; i++)
    {
        set_up(p, 0, len - i);
        p[0] = p[0] ^ p[len - i];//使用异或交换两个元素的值，（为了不开辟新的空间）
        p[len - i] = p[0] ^ p[len - i];
        p[0] = p[0] ^ p[len - i];
    }
}

int set_up(int* p, int i,int len)
{
    int tmp;
    if (2 * i + 1 == len) { 
        if (p[i] < p[len]) { tmp = p[i]; p[i] = p[len]; p[len] = tmp; }
        return 0;
    }
    if (2 * i + 1 > len) return;
   set_up(p, 2 * i + 1, len);

   set_up(p, 2 * i + 2,len);
   
   if (p[2*i+1] >= p[2*i+2] && p[2*i+1] > p[i]) { 
       tmp = p[i]; p[i] = p[2*i+1]; p[2*i+1] = tmp;
   }
   if (p[2 * i + 2] >= p[2 * i + 1] && p[2 * i + 2] > p[i]) { 
       tmp = p[i]; p[i] = p[2 * i + 2]; p[2 * i + 2] = tmp;
   }
}