手撕排序算法2：堆排序和直接选择排序（上）

补充:堆的知识点
堆的逻辑结构是一颗完全二叉树
堆的物理结构是一个数组
也就是说,给我们是一个数组,可是我们要把它想象成一个完全二叉树来做
通过下标父子结点关系
leftchild = parent * 2 + 1;
rightchild = parent * 2 + 2;
parent = (child - 1) / 2;(child可以是左孩子,也可以是右孩子)

堆的两个特性
1.结构性:用数组表示的完全二叉树
2.有序性:任意节点的关键字是其子树所有结点的最大值
3.堆的两种分类
最大堆(MaxHeap):也称为大顶堆(最大值)
最小堆(MinHeap):也称为小顶堆(最小值)
3.大堆:要求树中所有的父亲都大于等于孩子
小堆:要求所有的父亲都小于等于孩子
堆只有两种:大堆,小堆,其余的都不是堆,注意有些选择题常考堆的判别
大堆:堆顶数据是最大的
小堆:堆顶数据是最小的

> 堆排序(Heapsort)
> 是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。
> 它是通过堆来进行选择数据。
> 需要注意的是排升序要建大堆，排降序建小堆。这一点我们在后面后给大家进行解释
> 而给我们的数组又不一定是堆
> 所以我们要先把该数组转变为堆
> 然后再利用堆的特性来进行堆排序

//建小堆
//记住一句话:物理上我们操纵的是数组,脑子里我们操纵的是二叉树
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustDown(int* a,int n,int root)//root传入0,即根节点的下标
{
  int parent = root;
  int child = root * 2 + 1;//假设左孩子小,右孩子大
  while (child < n)//child>=n时数组越界
  {
    //1.选出左右孩子中小的那一个
    if (child + 1 < n && a[child] > a[child + 1])//左孩子大于右孩子,
    //child+1 < n:用来防止因为某个结点下方因为没有右孩子只有左孩子而产生数组越界
    {
      child++;//假设不成立,则将小孩子更新为右孩子
    }
    if (a[child] < a[parent])//孩子小于父亲,需要交换
    {
      Swap(&a[child], &a[parent]);//交换孩子和父亲
      parent = child;//更新父亲
      child = parent * 2 + 1;//更新孩子
    }
    else
    {
      break;//孩子大于等于父亲,无法交换,直接break
    }
  }
}

只需要修改我在下面代码中注释的地方即可,Swap函数见上面
void AdjustUp(int* a,int n,int root)//root传入0,即根节点的下标
{
  int parent = root;
  int child = root * 2 + 1;
  while (child < n)
  {
    if (child + 1 < n && a[child] < a[child + 1])//这里我们选出左右孩子中大的那一个
    {
      child++;
    }
    if (a[child] > a[parent])//这里只有当父亲小于孩子的时候才会交换
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

> 因为堆的物理结构是一个数组,数组最后一个元素的下标是n-1
> 也就是说最后一个叶子节点是的下标是n-1,而且不难发现最后一个非叶子结点就是最后一个叶子节点的parent
> 又因为我们在上面提到过
> parent=(child-1)/2
> 所以最后一个非叶子结点的下标值为(n-1-1)/2
> 而且最后一个非叶子结点之前的所有结点都是非叶子结点
> 下面我们来看一下代码

void HeapSort(int* a,int n)
{
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);//你没看错,将一个普通数组构造为一个小堆就是这么简洁,也就是从最后一个非叶子节点开始调整一直调整到根节点为止
  }
  //到现在为止我们堆排序的建堆工作就完成了
}

void HeapSort(int* a,int n)
{
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustUp(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

void HeapSort(int* a,int n)
{
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustUp(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();//生成100000个随机数
    a2[i] = a1[i];//保证所有的数组中的元素均相等
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
  }
  int begin1 = clock();//clock()获取到系统运行到这里的毫秒数
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a5, 0, N - 1);
  int end5 = clock();
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
}