Chinaunix首页 | 论坛 | 博客
  • 博客访问: 54333
  • 博文数量: 5
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 149
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-30 10:12
个人简介

记录学习、工作的点点滴滴

文章存档

2014年(5)

我的朋友

分类: LINUX

2014-09-09 22:26:56

 

14为比较排序,比较排序的时间下届为N*lgN,所以堆排序和归并排序是渐进最优的比较排序算法。而快速排序则是排序大数组的最常用算法。

1、         插入排序:每插入一个元素,就需要和已排序的数据进行比较,并且移动相关数据。所以效率较低,时间复杂度为O(n^2)

2、         归并排序:分解待排序的N个元素序列成各具N/2个元素的两个子序列;使用归并排序递归的排序两个子序列;合并两个已排序的子序列以产生排序的答案。时间复杂度为 N*lgN。很多时候我们需要分而治之的思想来解决问题:将问题分解为几个规模更小的问题,各自解决这些小问题,最后合并得到答案。在求解小问题的过程中,我们递归的使用这种思想。

3、         堆排序:堆排序分为两步,建堆和排序, 时间复杂度也是N*lgN

堆是一颗完全二叉树。

小根堆:父结点小于等于子结点。

大根堆:父结点大于等于子结点。

下面的操作以大根堆为例,小根堆类似。

维护堆操作:将一个结点调整到合适的位置来维护堆的性质,时间复杂度为 lg2n

建堆:将一组无序数据构造成堆。从底向上对每个元素执行(维护堆操作),简单估算时间复杂度为nlg2n,但是严格的证明结果是,该复杂度为n,线性时间。

堆排序:时间复杂度为 nlg2n

新增结点,删除结点:都是调整该结点到合适的位置,即维护堆操作。时间复杂度为 lg2n

取最大值:第一个元素就是,所以时间复杂度为O(1)。非常适合做优先队列。

4、         快速排序:随机选择一个数字,比它小的放前面,比它大的放后面,这样前半部分一定小于后半部分。每个部分递归调用快速排序。期望时间复杂度为N*lgN,最坏时间复杂度是O(n^2)。实际应用中通常比堆排序快。

57为线性时间排序:

5、计数排序:每个数都在一个小区间(0 ,K)之间。对每一个输入元素X,确定小于X的元素个数,利用这一信息,就可以直接把X放到数组的合适位置上面了。

6、      基数排序:对数字的每一位进行计数排序。时间复杂度是(位数*N)。虽然基数排序是线性时间复杂度,但是并不一定比快速排序快。这和底层硬件(缓存命中)、输入数据的特征、内存等很多因素相关。

7、      桶排序:适用于数据独立,均匀的在某个区间内分布。将每个数据映射到桶上,映射位置相同则用链表,然后每个链表独立排序即可。

中位数算法:求一个数组中中间大小的数字,或者第i小的数字。

A、      这个算法的思想和快速排序的思想有点相似,随机选择一个数字,将小的放它前面,大的放它后面。一遍过后重新计算i的数值,然后只需要在其中一半里面继续查找,另外一半就补需要关心了。最坏的时间复杂度是O(n^2),期望为O(n)

B、      为了保证最坏时间复杂度为O(n),需要精心选择每次比较的数字。将数组按5个一组进行分配,找出每组的中位数。然后重复这个过程,直到找出这个用来分割的数字,然后用这个数字进行A操作。

阅读(3711) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~