八大排序之堆排序

思想：

1. 从最后一棵子树开始，从后往前调整
2. 每次调整，从上往下
3. 调整为大根堆

父子结点关联：（下标从0开始）

         父              子

          i          2*i+1,2*i+2

       (i-1)/2            i              

思路演绎：

• 下标从0开始作为二叉树的根节点，数据从上到下依次赋值，存放如图所示二叉树

        原始数据：7 4 9 5 12 6 8 3 10 23 11​​​​​
        

•  先对子树进行调整：绿->红->蓝->黄下->黄上的顺序看。 
• 步骤：

1. 从后往前（从下往上）调整。在该图中也就是从最后一棵子树（下标为4）开始，找左右孩子最大值（23），与此时子树的根结点值（12）交换。
2. 每次调整后从上往下再调一遍。此时根结点4的子树调整完毕，需要从根节点为0开始从上往下遍历检查是否还有根节点值小于左右字数的情况存在，如有，进行调整
3. 持续1和2的步骤，直至根节点的值均大于左右孩子。

         

         调整后为：23 12 9 10 11 6 8 3 5 4 7

                

•  交换数据：根与待排序的最后一个交换，并且再次调整顺序
• 步骤：

1. 先对根节点为0的子树的值(23)与最后一个结点(7),得到如下左图所示
2. 对左图重新调整顺序，得到右图所示
3. 重复1和2的步骤，直至待交换数据下标为0，也就是待交换数据与交换数据根节点一致。

           

         循环之最后的结果图为：

        

---

时间复杂度：O(nlogn)   //从上往下调整的时候需要遍历->O(n),根节点与左右孩子交换时i=2*i+m ->O(logn).因此循环嵌套时，总时间复杂度为O(nlogn) 

空间复杂度：O(1)

稳定性：不稳定

---

 代码：

//大根堆
//调整为大根堆:左右孩子最大值和根交换的函数
void HeapAdjust(int* arr, int start,int end)
{
    int temp = arr[start];
    for(int i=2*start+1;i<=end;i=2*i+1)//2*start+1左孩子
    {
         if(i<end&&arr[i]<arr[i+1])//有右孩子并且小于右孩子
        {
             i++;
         }//i一定是左右孩子最大值
         if(arr[i]>temp)
         {
              arr[start]=arr[i];
              start=i;
             }
        else
          break;
    }
    arr[start]=temp;
}
void HeapSort(int* arr, int len)
{
    int i;
    //1.左右孩子最大值和根交换
    for (int i = (len - 1 - 1) / 2; i >= 0; i--)
    {
        HeapAdjust(arr,i,len-1);//i:根开始下标；len-1：根截止下标（均设置为len-1)
    }
    //2.下标为0的根开始和待排序的最后一个值交换//3.再次调整
    int temp;
    for (int i = 0; i < len - 1; i++)//=len-1时没必要再和自己交换而且也不需要再次调整
    {
        temp = arr[0];
        arr[0] = arr[len - 1 - i];//下标从0开始 len-1
        arr[len - 1 - i] = temp;
        HeapAdjust(arr, 0,len - 1 - i - 1);
    }
}

void Show(int* arr,int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    int arr[] = { 6,4 ,7,8,10,-5,90,34,55};
    Show(arr,sizeof(arr) / sizeof(arr[0])); 
    printf("\n ");
    HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
    Show(arr, sizeof(arr) / sizeof(arr[0]));
}

运行结果：