[数据结构]排序之 堆排序详解

目录

一、建堆

二、利用堆删除思想来进行排序 

三、堆排序的时间复杂度 

一、建堆

• 升序：建大堆
• 降序：建小堆

//排升序建大堆
void HeapSort(int* a, int n)
{
       //建大堆
       for (int i = 1; i < n; i++)
       {
              AdjustUp(a, i);
       }
}

void HeapSort(int* a, int n)
{
       //向下调整建堆
       for (int i = (n - 1 - 1) / 2; i >= 0;--i)//先找到最后一个非叶子结点即上图的6 n-1是最后一个数据的下标，再-1除以2就是父节点
       {
              AdjustDown(a, n, i);
       }
}

二、利用堆删除思想来进行排序 

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

三、堆排序的时间复杂度 

所以如果用来排序的话，无论是向上调整还是向下调整建堆，总的时间复杂度都是O(N*logN) 

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
       int child = parent * 2 + 1;//先默认左孩子大
       while (child < n)
       {
              //选出左右孩子中大的那一个  右孩子和左孩子的关系：大一
              if (child + 1 < n && a[child + 1] > a[child])
              {
                      ++child;
              }
              if (a[child] > a[parent])
              {
                      Swap(&a[child], &a[parent]);
                      parent = child;
                      child = parent * 2 + 1;
              }
              else
              {
                      break;
              }
       }
}
//O(n*logn)
//排升序建大堆
void HeapSort(int* a, int n)
{
       //向下调整建堆
       for (int i = (n - 1 - 1) / 2; i >= 0; --i)//n-1是最后一个数据的下标，再-1除以2就是父节点
       {
              AdjustDown(a, n, i);
       }
       int end = n - 1;
       while (end > 0)
       {
              Swap(&a[end], &a[0]);
              AdjustDown(a, end, 0);
              --end;
       }
}
int main()
{
       printf("调整前:");
       int a[10] = { 2,1,5,7,6,8,0,9,3 };
       for (int i=0;i<9;i++)
       {
              printf("%d ", a[i]);
       }
       printf("\n");
       HeapSort(a, 9);
       printf("调整后:");
       for (int i = 0; i < 9; i++)
       {
              printf("%d ", a[i]);
       }
       return 0;
}