内核sort.c 分析

最近,有人面试被问到sort了,总结文档一小篇。

内核数据结构与算法 –sort.c
sort.c 的定义位置: 内核/inclde/linux/sort.h
sort 源码的位置: 内核/lib/sort.c
我们来看看sort.h 和 sort.c 的内容,sort 是以库的是形式存在,实现上使用内核倒入符号:
sort.h 只进行了定义。

 

由此可见linux使用的是堆排序,时间复杂度n(logn).排序时间为O(n log n)的平均和最坏情况下。而qsort比堆排序快20%左右的平均值,它有可利用的 O(N * N)最坏情况下的行为和额外的内存要求,所以不太适合内核使用。堆排序就是那个二叉树排序,每个节点的值必须小于自己的父亲节点的值。内核实现使用了数组存储方式罢了。
第一步:
调整堆 即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
第二步:
将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。
堆排序其实也是一种选择排序,是一种树形选择排序。只不过直接选择排序中,为了从R[1…n]中选择最大记录,需比较n-1次,然后从R[1…n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过,而树形选择排序恰好利用树形的特点保存了部分前面的比较结果,因此可以减少比较次数。对于n个关键字序列,最坏情况下每个节点需比较log2(n)次,因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序,不适合记录较少的排序
一个参考博客:http://www.cnblogs.com/jingmoxukong/p/4303826.html

本文固定链接: http://zmrlinux.com/2017/03/08/%e5%86%85%e6%a0%b8sort-c-%e5%88%86%e6%9e%90/ | Kernel & Me

该日志由 root 于2017年03月08日发表在 Linux kernrl, 数据结构,来啦!, 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 内核sort.c 分析 | Kernel & Me