数据结构 【堆排序】

        上面两篇文章中，我们可以相识到大堆的堆顶存放的是堆中最大的元素，小堆的堆顶存放的是堆中最小的元素。利用堆的这个属性就可以实现排序的目的。
        如果排升序，那么利用大堆选取堆中最大的数据放置在堆顶，将堆顶元素与堆中末了一个元素举行交换，将最大的元素清除在外举行向下调解，循环遍历整个堆就可以得到原数据的升序分列。如果排降序，同样的原理，先选取小堆的堆顶，得到堆中最小的元素，将其与堆中末了一个元素举行交换位置，将末了一个元素清除在外，再举行向下调解，遍历整个堆，就会得到原数据的升序分列。总结一下：由于堆的特别属性，排升序时利用大堆，排降序时利用小堆。
        在排序之前我要声明的是，不是要创建一个堆如许的数据结构来举行排序。而是举行模仿堆的属性举行排序。渴望是有一组存放在数组中的数据，通过堆排序函数实现排序的目的。由于升序降序的焦颔首脑是划一的，这篇文章选取模仿建大堆的过程实现数据的升序排序。下面正文开始！
1、预备工作

        先给出本次建堆的需求：将一组存放在数组当中的数据举行升序排序，渴望输出原数据的升序分列。

2. #include <stdio.h>
4. int main()
5. {
6.         int arr[] = {5,3,7,8,2,4,1,6,0,1,-1,-100,50 };
7.         int sz = sizeof(arr) / sizeof(arr[0]);
8.         HeapSort(arr, sz);
9.         int i = 0;
10.         for (i = 0; i < sz; i++)
11.         {
12.                 printf("%d ", arr[i]);
13.         }
14.         printf("\n");
15.         return 0;
16. }

复制代码

2、堆排序

        在堆实现这篇文章中我提到堆在插入后要举行向上调解已包管堆的属性：大堆堆顶为最大的数据，小堆堆顶为最小的数据。现在我们假设数组的第一个元素就是堆顶，须要做的是将从第二个元素到末了一个元素举行向上调解以得到堆顶元素，升序要建大堆，我们这里就是为了得到最大的元素。
2.1、模仿向上调解建堆

        这里将向上调解封装成一个函数，方便反面的调用。

2. void Swap(int* ps1, int* ps2)
3. {
4.         int tmp = *ps1;
5.         *ps1 = *ps2;
6.         *ps2 = tmp;
7. }
9. void AdjustUp(int* arr,int child)
10. {
11.         assert(arr);
12.         int parent = (child - 1) / 2;
13.         while (child > 0)
14.         {
15.                 if (arr[child] > arr[parent])
16.                 {
17.                         Swap(&arr[child], &arr[parent]);
18.                         child = parent;
19.                         parent = (child - 1) / 2;
20.                 }
21.                 else
22.                 {
23.                         break;
24.                 }
25.         }
26. }

复制代码

        这里的逻辑和上文中是划一的，当子结点的数据小于父结点的数据时就举行交换，当子结点的下标小于即是0时就跳出循环。这里我们就可以将数据建成一个大堆并可以获取原数据中最大的元素。
2.2、 模仿向下调解排序

        这里将向下调解封装成一个函数：

2. void AdjustDown(int* arr, int size, int parent)
3. {
4.         assert(arr);
5.         int child = parent * 2 + 1;//默认左边的子结点最大
6.         while (child < size)
7.         {
8.                 if (child + 1 < size && arr[child + 1] > arr[child])
9.                 {
10.                         child++;//右边子结点存在且满足条件进行调整
11.                 }
12.                 if (arr[child] > arr[parent])
13.                 {
14.                         Swap(&arr[child], &arr[parent]);
15.                         parent = child;
16.                         child = parent * 2 + 1;
17.                 }
18.                 else
19.                 {
20.                         break;
21.                 }
22.         }
23.        
24. }

复制代码

        如果排升序，那么利用大堆选取堆中最大的数据放置在堆顶，将堆顶元素与堆中末了一个元素举行交换，将最大的元素清除在外举行向下调解，循环遍历整个堆就可以得到原数据的升序分列。

2. void HeapSort(int* arr, int sz)
3. {
4.         assert(arr);
5.         int i = 0;
6.         for (i = 1; i < sz; i++)
7.         {
8.         //使用向上调整建堆，从第二个元素开始模拟堆插入过程。
9.                 AdjustUp(arr, i);
10.         }
12.         int end = sz - 1;
13.         for (i = end; i > 0; i--)
14.         {
15.                 Swap(&arr[0], &arr[i]);//将堆顶与末尾进行交换
16.                 AdjustDown(arr, i,0);//这里注意堆的尾结点位置为i
17.         }
19. }

复制代码

        那么现在全部的工作已经预备停当，运行步伐可以得到效果：

 3、时间复杂度

        3.1、向上调解建堆

         向上调解是从堆的末了一个元素举行的，假设末了一层元素的高度为h，那么这层结点最坏的情况下须要向上交换h-1次（由于它的上面另有h-1层）。假设整个向上调解的次数为T(N)，那么T(N)=每一层结点各自的调解次数之和。

        这里利用错位相减法求T(N):

         以是带入h的值，有：

        3.2、向下调解建堆

        与向上调解差异的是，向下调解从倒数第二行开始，这就注定着它的时间复杂度要优于向上调解。那么整个向下调解的次数T(N)为：

4、堆排序优化 

        根据上面复杂度的盘算，我们发现向下调解要优于向上调解，实际上在建堆的过程中可以完全利用向下调解。思绪如下：

        找到末了一个结点的父节点，举行子树的向下调解得到子树的最大值。依次按照图中的序次遍历每个子树就可以得到最大值。
        代码实现如下：

2. void HeapSort(int* arr, int sz)
3. {
4.         assert(arr);
5.         int i = 0;
6.         int end = sz - 1;
7.         for (i = (end - 1) / 2; i >= 0; i--)
8.         {
9.                 AdjustDown(arr, sz, i);//父结点的下标为i
10.         }
12.         end = sz - 1;
13.         for (i = end; i > 0; i--)
14.         {
15.                 Swap(&arr[0], &arr[i]);//将堆顶与末尾进行交换
16.                 AdjustDown(arr, i,0);//这里注意堆的尾结点位置为i
17.         }
19. }

复制代码

        上述代码在建堆过程中可以恰当优化代码。但团体代码的时间复杂度仍为O(N*logN)