本文共 2219 字,大约阅读时间需要 7 分钟。
#题外话堆排序比之前的简单选择、冒泡算法、快速排序算法复杂一些,因为用到了树形数据结构,但是本文使用了数组实现完全二叉树,因此也比较简单。C语言初学者,可以简单了解其思想,具体的知识掌握可以参照数据结构等专业课程学习。
ps:昨天因为学习实在太晚,未及时更新,抱歉哈。学习C语言之余,觉得C语言编程,最重要的就是C语言语法+数据结构+算法,掌握这三方面基本上可以应付各种编程问题。
为什么学习排序算法,可以参见前面文章~[C语言必学的12个排序算法:基础知识 (第0篇)]
选择排序其实可以有简单选择排序、树形选择排序。
其中堆排序是一种高效的树形选择排序。
简单选择排序时间复杂度是O(n^2),每趟子排序需要比较O(n)次。
树形选择排序通过减少每趟子排序比较次数,减少时间复杂度,基本思想是每趟子排序,对整个数据记录关键字重复两两比较(和锦标赛赛制一样),直至选出最小的关键字记录为止,这样每趟子排序只需要比较O(logn)次,重复n次,即可有序,时间复杂度为O(nlogn)。
普通的树形选择排序需要的辅助空间较多、存在多余的比较的缺点,堆排序改进这些缺点,只需要1个辅助空间,堆排序的时间复杂度是O(nlogn),同样也是不稳定的内部排序。
与快速排序比较,优势是最坏的情况,堆排序的时间复杂度同样是O(nlogn),快速排序平均性能比堆排序好,但是最坏情况时间复杂度是O(nlogn)。
堆排序涉及的知识点较多,主要包括堆的定义、完全二叉树,对于C语言初学者来说,具体理论知识可以参见《数据结构》相关课本书籍。
1.完全二叉树
叶子结点只能出现在最后一层或倒数第二层的二叉树。通俗来说,树的父节点都有两个孩子结点,除非是最后一层或倒数第二层的父节点可以有1或0个孩子结点。
2.堆定义
堆首先是完全二叉树,根据父节点是否比孩子节点大,分为大顶堆和小顶堆。
大顶堆:完全二叉树中所有的父节点必须大于等于两个孩子结点,这样树的根结点就是整个树结点中最大值。
小顶堆:完全二叉树中所有的父节点必须小于等于两个孩子结点,这样树的根结点就是整个树结点中最小值。
3.排序过程
以从小到大排序为例,对整个数据记录序列初始建立“大顶堆”,然后根结点为最大关键字,和序列最后一个关键字记录交换,继续对剩下的前n-1个记录序列进行调整,重新变成新的“大顶堆”,如此反复,每次可以得到当前子序列最大的关键字,最后即可得到从小到大的序列。
实现要点:
*/#include// 对范围[low,high]数据记录筛选调整建立堆void adjust_heap(int a[],int low, int high){ int t = a[low]; int i; // 注意数组下标从0开始 // 二叉树结点编号需要从1开始 // 父节点与孩子结点比较大小,沿着元素路径向下 for(i=2*(low+1); i<=(high+1); i *= 2) { // 比较左右孩子结点,如果右孩子大,选择右孩子 if(i<=high && a[i-1] =a[i-1]) break; // 否则调整交换位置 // 此时不需要给a[i-1]赋值,节约操作 a[low] = a[i-1]; low = i-1; } a[low] = t;} void heap_sort(int a[], int length){ int i,t; // 初始建成大顶堆 for(i=length/2-1; i>=0; i--) { adjust_heap(a, i, length-1); } // 每趟选出最大元素和当前最后一个元素交换,再调整成堆 for(i=length-1; i>=0; i--) { t = a[0]; a[0] = a[i]; a[i] = t; adjust_heap(a, 0, i-1); }}int main(void){ int a[10] = {4,3,1,2,6,5,0,9,8,7}; heap_sort(a, 10); int i; for(i=0; i<10; i++) printf("%d ", a[i]); return 0;}
其实做为一个学习者,有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。
转载地址:http://vdjwi.baihongyu.com/