1. 算法思想:

   1. 将数组中的数据建立成所有根结点大于其左右子树的完全二叉树，即大根堆
   2. 然后将第一个堆顶结点，即root结点，也是当前未排序的最大数据，和最后未排序的数据的位置交换，结果类似冒泡排序排好了一个数据，那么现在那个最后未排序的位置就是当前的最大的数据，也就排好了一个数据
   3. 但是因为交换数据，现在的root结点的数据不一定就是最大的，那么就还需要调整堆，使其满足大根堆条件。
   4. 重复上述过程，就可以得到升序序列;反之，建立小根堆可以得到降序序列。

2. 代码：

   //k 是要调整的结点在数组中的下标，在createHeap中传入的值是从最后一个非叶子结点的下标依次递减到0,表现为从中点处依次向上调整堆
   //但是在HeapSort循环中，根据上述算法，每次调整的都是堆顶的root结点，即第一个结点，k=0。
   //n 是还要排序n个数，第n个数也要排序，所以while循环里的条件，注意判断j等于n的情况
   //j 是i的左子树结点,为2*k+1的原因是数组下标从0开始，经过试验规律得到i的左子树下标为2*k+1
   void adjustHeap(int array[], int k, int n)
   {
   	int i = k, temp;
   	int j = 2 * k + 1;
   
   //如果j的值已经大于要排序的最后一个值的下标，说明i不存在左子树，根据完全二叉树的定义，肯定没有右子树，那么这个i结点一定是满足大根堆的，无需调整。
   	while (j <= n)
   	{
   	//如果j+1的值小于等于要排序的最后一个值的下标，那么i不仅有左子树，还有右子树，那么就要比较右子树的数据是否大于左子树，如果是的话，j++，使j的值为i的最大子树的下标。
   		if (j + 1 <= n && array[j] < array[j + 1])
   			j++;
   
   		//如果从i向下检查时，满足这个条件，就说明从这个结点开始往下的子树一定满足大根堆条件，就可以不用再检查，可以直接结束循环了。
   		//[当然，原因分两种情况。第一：是在创建堆时，i是最后一个非叶子结点，其后一定的都是叶子结点，一定满足大根堆，而i以前的非叶子结点进行判断时，因为后面一定已经调整好了，也一定满足大根堆。第二：在HeapSort循环里调整的话，和上面其实一样，每次交换可能只破坏了一个局部的大根堆，当把这个局部的调整回来时，其后面的结点就和之前一样，不受影响了。]
   		if (array[i] >= array[j])
   			break;
   		//如果当前根结点i的值不是其左右字数中最大的，那么就和那个最大的数交换，使其满足大根堆条件
   		if (array[i] < array[j])
   		{
   			temp = array[i];
   			array[i] = array[j];
   			array[j] = temp;
   
   			//因为交换了值，可能破坏大根堆的条件，那么就要循环向下判断大根堆条件是否满足
   			//这里还有技巧，只需要检查与i交换的j往下的子结点即可，不用检查那个没有发生交换的结点。
   			i = j;
   			j = i * 2 + 1;
   		}
   	}
   }
   
   void createHeap(int array[], int n)
   {
   	//从当前的最后一个非叶子结点开始,从后往前[以数组的形式看]，从下到上[以二叉树的形式看]创建堆
   	for (int i = n / 2 - 1; i >= 1; i--)
   		adjustHeap(array, i, n);
      }
   void HeapSort(int array[], int n)
      {
   	int temp;
   	createHeap(array, n);
   	//创建好大根堆后，先把最大的数据(n-1)换到最后面，再将被破坏的大根堆调整，使其满足大根堆条件。
   	//再重复上述步骤
   	for (int i = n - 1; i >= 1; i--)
   	{
   		temp = array[0];
   		array[0] = array[i];
   		array[i] = temp;
   		adjustHeap(array, 0, i - 1);
   	}
   }