当前位置:   article > 正文

八大排序之一:堆排序(详解)_堆排序 csdn

堆排序 csdn

目录

一、八大排序:

二、堆的基本知识

1、堆的概念

2、堆的构建

三、堆排序的实现 

1、排序原理

2、如何存储&找孩子/父亲结点

3、向上/下调整函数(实现堆排序的基本函数)

I) 向上调整(大堆为例)

II)向下调整(大堆为例)

4、 开始排序

方法1:开辟额外空间

I) 建堆

II)排序

方法2:不开辟额外空间(推荐)

I) 建堆

II)排序

5、建堆和排序注意事项

6、时间复杂度


一、八大排序:


二、堆的基本知识

       

1、堆的概念

堆是个单调递增/减的满/完全二叉树

如图所示:

每个结点都他的孩子结点,我们就称这样的数据结构为小堆

图1是大堆,图2是大堆,图3不是堆(不是完全/满二叉树)

        

2、堆的构建

建堆的目的大部分是为了排序或者topk问题

  1. 不用链表建堆(不好找数据以及移动数据
  2. 用顺序表建堆
  3. 采用尾插,不能使用头插
  4. 采用头删(此处的头删,指的是删除头处的数值,而不是删除头)

建堆代码: 

  1. typedef int HeapDataType;
  2. typedef struct Heap//构建顺序表
  3. {
  4. HeapDataType* arr;
  5. int size;//堆的数据长度
  6. int capacity;//堆的最大容量
  7. }Heap;

三、堆排序的实现 

                

1、排序原理

利用建大/小堆来找出一组数中的最大/小数据

再多次对剩下的数据继续进行建堆,就可以选出第2大/小的,第3大/小的......(这里需要对根的值进行一个调整,使其不会对剩下的数据产生影响,后续会说明)

                

2、如何存储&找孩子/父亲结点

         

任何一个数据都要有一个存储方式,前文提到,堆用顺序表存储 

既然要排序,那么找数据就特别关键,而找数据和建堆用的就是父亲节点孩子结点的一个”比较交换“来实现查找和交换

这里有一个公式:(这里的值都是以下标为准,同时parent和child是相对的)

leftchild==parent*2+1

rightchild==parent*2+2

parent==(child-1)/2        (左右孩子都是这样)

                 

3、向上/下调整函数(实现堆排序的基本函数)

I) 向上调整(大堆为例)

孩子和父亲比较,孩子大于父亲就交换

!!该例子不满足向上调整的前提,不能进行向上调整,此处只是为了说明何为向上调整!!

向上调整的前提!!!!!

:该节点的父树是大/小堆,例:

9和5的父亲是7

结点7、2、0构成的结构不是堆,所以不能进行向上调整 

II)向下调整(大堆为例)

父亲和孩子比较,父亲小于孩子就交换

 向下调整的前提!!!!!

:该节点的子树是大/小堆,例:

7的孩子是9,5

而9,5每个结点的孩子都是NULL,所以构成的结构是堆,能进行向下调整 

 这里对代码有疑惑不用急,这里只是展示两个函数,具体的步骤后面会补充

代码实现(递归):

  1. //以下均为建大堆代码
  2. void swap(HeapDataType*p1,HeapDataType*p2)//交换两个结点的值
  3. {
  4. HeapDataType tmp = *p1;
  5. *p1 = *p2;
  6. *p2 = tmp;
  7. }
  8. //向上调整建堆
  9. void Adjustup(HeapDataType* arr, int child)//arr是存储数据的顺序表,child是孩子结点的下标
  10. {
  11. assert(arr);//断言,防止穿空指针
  12. int parent = (child - 1) / 2;//定位父亲结点
  13. while (child != 0)//判断结束条件,防止溢出
  14. {
  15. if (arr[parent] < arr[child])//如果孩子结点大于父亲结点,就交换。若用>则是建小堆
  16. {
  17. swap(&arr[parent], &arr[child]);
  18. }
  19. child = parent;
  20. parent = (child - 1) / 2;
  21. //孩子和父亲都向上移,进行一轮新的比较
  22. }
  23. }
  24. //向下调整建堆
  25. void Adjustdown(HeapDataType* arr, int parent,int size)//arr是存储数据的顺序表,parent是父节点的下标,size是数组长度
  26. {
  27. assert(arr);
  28. int child = parent * 2 + 1;//定位孩子结点
  29. while (child < size)//判断结束条件,防止溢出
  30. {
  31. if (child + 1 < size)//防止下一步的child+1访问越界
  32. child = arr[child] > arr[child + 1] ? child : child + 1;//判断左右孩子哪一个更大,选取更大的
  33. if (arr[parent] < arr[child])//如果孩子结点大于父亲结点,就交换
  34. {
  35. swap(&arr[parent], &arr[child]);
  36. }
  37. parent = child;
  38. child = parent * 2 + 1;
  39. //孩子和父亲都向下移,进行一轮新的比较
  40. }
  41. }

        

4、 开始排序

     

方法1:开辟额外空间  

空间复杂度O(n)

I) 建堆

以升序:建大堆为例

将一个已知数组的元素依次插入到一个空数组中,每次插入的时候都要进行1次向上调整。

最终就建好了一个大堆,如上图所示。

II)排序

这里我们发现该数组  {10,7,9,2,0,5,1}  并不是有序的,这是因为我们还没有进行排序,只是进行了建堆。

注意:这里排序的过程用到了删除的思想!

Step1首尾元素交换,然后我们逻辑上把10移出数组。

                实际上:{ 1,7,9,2,0,5,10 }                我们认为:{ 1,7,9,2,0,5 }

Step2:对删掉后的剩余数据从arr[0]开始,继续向下调整建堆(因为此时根的子树必然满足堆结构)

建好后的堆是 { 9,7,5,2,0,1 };

Step3:继续对剩下的元素 {9,7,5,2,0,1} 进行Step1,直到最后数组中 “只剩” 一个元素,此时数组如下

这样我们就排好序了。

可惜这样的排序,不会修改原数组,如果需要修改原数组,则还需要进行一遍覆盖。

  1. int main()
  2. {
  3. int arr[] = { 2,10,9,7,0,5,1 };//待排序数组
  4. int arr_sort[7] = { 0 };//用来排序的数组
  5. int size = sizeof(arr) / sizeof(arr[0]);
  6. for (int i = 0; i < 7; i++)
  7. {
  8. arr_sort[i] = arr[i];//将数组中的元素一个一个传进待排序数组
  9. Adjustup(arr_sort, i);//每次传进一个元素都进行一次向上调整
  10. }
  11. while(size>1)//判断剩余未排元素数量
  12. {
  13. swap(&arr_sort[0], &arr_sort[size - 1]);//交换首尾元素
  14. size--;//“删掉”末尾元素
  15. Adjustdown(arr_sort, 0, size);//建大堆,将根的元素置成最大
  16. }
  17. return 0;
  18. }

         

方法2:不开辟额外空间(推荐)

空间复杂度O(1)

I) 建堆

以升序:建大堆为例

Step1:找到第一个非叶子结点

Step2:以这个结点为开始,对该节点进行向下调整。

Step3:调整完后,再依次向前遍历并调整(每个遍历到的元素都要调整),直到遍历并且调整完前面的所有结点为止

II)排序

 Step4:再用方法1的删除思想就可以完成数组的排序了

  1. int main()
  2. {
  3. int arr[] = { 2,10,9,7,0,5,1 } ;//待排序数组
  4. int size = sizeof(arr) / sizeof(arr[0]);
  5. int start = (size - 2) / 2;//找到第一个非叶子结点
  6. for(int i=start;i>=0;i--)//遍历完第一个非叶子结点往前的全部
  7. {
  8. Adjustdown(arr, i ,size);//每次遍历一个元素时,都要向下调整
  9. }
  10. while(size>1)//判断剩余未排元素数量
  11. {
  12. swap(&arr[0], &arr[size - 1]);//交换首尾元素
  13. size--;//“删掉”末尾元素
  14. Adjustdown(arr, 0, size);//建大堆,将根的元素置成最大
  15. }
  16. return 0;
  17. }

        

5、建堆和排序注意事项

I)为什么子树和父树一定要是大/小堆?

如果我拿出如上结构,阁下又要如何应对呢

II)前文提及:升序建大堆,降序建小堆,那为什么不能反过来呢?

你的思路一定如下:

但此时,难题就来了!

1、如果这样搞

        

2、如果这样搞这都不是堆了

        

6、时间复杂度

这里讨论的是方法2,也是最优时间复杂度

先看建堆的时间复杂度 (这里是建堆,不是排序)    

由于是做最坏打算,所以我们认为,每一个数都要移动到最底层 & 该树是满二叉树

                 

排序的时间复杂度

所以,T(n) = n * log n;

加上前面的建堆时间,总共:T(n)= n +(n * log n)

所以时间复杂度是T(n)=O(n*log n)

                        

                        

                        

以上就是堆排序的全部内容,如果您有什么问题或者建议,随时欢迎与作者讨论! 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/615282
推荐阅读
相关标签
  

闽ICP备14008679号