堆排序精讲

简介: 堆排序精讲

堆排序的时间复杂度是n*logn,可以说吊打冒泡排序(n^2)。是建立在堆这种数据结构的理解上演化出来的一种排序方式。上篇文章对堆这种数据结构已经有详细的介绍。这篇文章就用堆这种数据结构基础搞定堆排序。

一.堆排序思路

堆排序的思路是:若排降序,将给定数据(数组中)建小堆,因为小堆堆顶数据一定最小,每次互换堆顶元素和最后一个元素,将最后一个元素分隔开,然后从堆顶开始向下调整,继续互换堆顶元素和倒数第二个元素,再将倒数第二个分隔开,再从堆顶向下调整,循环这个过程,直到只剩下一个元素为止。若排升序,则建大堆,后续相同。

二.建堆

堆的存储结构是数组,逻辑结构是完全二叉树。要想实现堆排序,首先需要建堆这里提供两种建堆方法:

一.向下调整建堆

first step,找到尾节点的父亲节点

注:灰色数字为数组中的下标

second step,从这个节点开始向下调整,下标顺序为:3->2->1->0

注:红色的数字为向下调整顺序:1->2->3->4

二.向上调整建堆

向下调整建堆的本质就是依次将数据插入堆

插入顺序为:1->2->3->4->5->6->7->8

每次向上调整,将数据一个一个插入堆。可保证最后是一个堆。

三.排序(这里是降序)

降序需要建小堆,排序的逻辑就是每次交换堆顶元素和堆尾(下标为end)元素,分离堆尾元素。

交换完毕后,将堆顶元素向下调整,重新建堆,堆顶元素又成为剩下数据中的最小数据,再交换堆顶元素和堆尾元素(下标为end),再分离,循环往复,直到堆里只整下一个元素。

四.代码实现及测试

1. void swap(int* pa, int* pb)//交换函数
2. {
3.  int tmp = *pa;
4.  *pa = *pb;
5.  *pb = tmp;
6. }
7. void AdjustDown(int* a, int size, int parent)//建小堆的向下调整
8. {
9.  int child = parent * 2 + 1;//左孩子
10.   while (child<size)
11.   {
12.     if (child+1<size&&a[child] > a[child + 1])//找到较小的孩子
13.       child++;
14. 
15.     if (a[parent] >a[child])
16.     {
17.       swap(&a[parent], &a[child]);
18.       parent = child;
19.       child = parent * 2 + 1;
20.     }
21.     else
22.       break;
23.   }
24. }
25. int main()
26. {
27.   int a[7] = {2,4,5,7,6,8,9};//想要排降序
28.   //建小堆
29.   int end = 6;//堆尾下标
30.   int parent = (end - 1) / 2;//堆尾节点的父亲节点下标
31.   while (parent >= 0)
32.   {
33.     AdjustDown(a, 7, parent);//这里用向下调整建堆
34.     parent--;
35.   }
36. //排序
37.   while (end > 0)//直到堆里只剩下最后一个数据
38.   {
39.     swap(&a[0], &a[end]);
40.     AdjustDown(a, end, 0);
41.     end--;
42.   }
43. //测试
44.   for (int i = 0; i < 7; i++)
45.   {
46.     printf("%d ", a[i]);
47.   }
48.   return 0;
49. }

代码测试结果


目录
打赏
0
0
0
0
0
分享
相关文章
数据结构算法--4堆排序
堆排序过程概述:建立大根堆,将堆顶最大元素移出并替换为末尾元素,调整保持堆性质,重复此过程直至堆为空,实现排序。时间复杂度为O(nlogn)。Python中可用heapq模块进行堆操作。
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
108 0
数据结构与算法学习十八:堆排序
|
8月前
|
数据结构与算法-归并排序
数据结构与算法-归并排序
43 2
数据结构与算法-插入排序
数据结构与算法-插入排序
43 2
[数据结构 -- 手撕排序算法第四篇] 堆排序,一篇带你搞懂堆排序
[数据结构 -- 手撕排序算法第四篇] 堆排序,一篇带你搞懂堆排序
|
9月前
|
数据结构与算法:归并排序
数据结构与算法:归并排序
99 7
数据结构与算法:快速排序
数据结构与算法:快速排序
61 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等