# 1. 堆排序
参考[出处][1]
## 1.1 二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
> * 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
> * 每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
## 1.2 堆的存储
一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
## 1.3 堆的操作——插入删除
**堆的插入**
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中
**堆的删除**
按定义,堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。下面给出代码:
个人总结:
所以堆排序就是在堆的基础上来排序。
**堆化数组**
## 1.4 堆排序
首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。
由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。有点类似于直接选择排序。
## 1.5 时间复杂度分析
时间复杂度 O(nlogn), 空间复杂度O(1). 从这一点就可以看出,堆排序在时间上类似归并,但是它又是一种原地排序,时间复杂度小于归并的O(n+logn)
排序时间与输入无关,最好,最差,平均都是O(nlogn). 不稳定
堆排序借助了堆这个数据结构,堆类似二叉树,又具有堆积的性质(子节点的关键值总小于(大于)父节点)
堆排序包括两个主要操作:
保持堆的性质heapify(A,i)
时间复杂度O(logn)
建堆 buildmaxheap(A)
时间复杂度O(n)线性时间建堆
> 对于大数据的处理: 如果对100亿条数据选择Topk数据,选择快速排序好还是堆排序好? 答案是只能用堆排序。 堆排序只需要维护一个k大小的空间,即在内存开辟k大小的空间。而快速排序需要开辟能存储100亿条数据的空间,which is impossible.
# 2. 快速排序
## 2.1 算法步骤
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种`分治的策略`,通常称其为`分治法(Divide-and-ConquerMethod)`。
该方法的基本思想是:
> 1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
```
static void quikSort(int s [], int l, int r) {
if (l < r) {
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j) {
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quikSort(s, l, i - 1); // 递归调用
quikSort(s, i + 1, r);
}
}
```
## 2.2 算法复杂度分析
我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50,正好是待排序的序列的中间值,因此递归树是平衡的,此时性能也比较好。
![此处输入图片的描述][2]
图9-9-7在最优情况下,Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就为.log2n.+1(.x.表示不大于x的最大整数),即仅需递归log2n次,需要时间为T(n)的话,第一次Partiation应该是需要对整个数组扫描一遍,做n次比较。然后,获得的枢轴将数组一分为二,那么各自还需要T(n/2)的时间(注意是最好情况,所以平分两半)。于是不断地划分下去,我们就有了下面的不等式推断。
> T(n)≤2T(n/2) +n,T(1)=0
T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n
T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n
……
T(n)≤nT(1)+(log2n)×n= O(nlogn)
也就是说,在最优的情况下,快速排序算法的时间复杂度为O(nlogn)。
在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为![此处输入图片的描述][3] ,最终其时间复杂度为O(n2)。
平均的情况,设枢轴的关键字应该在第k的位置(1≤k≤n),那么:
![此处输入图片的描述][4]
由数学归纳法可证明,其数量级为O(nlogn)。
就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。
可惜的是,由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。
# 3. 冒泡排序
冒泡排序是非常容易理解和实现,,以从小到大排序举例:
## 3.1 冒泡排序概述
> 设数组长度为N。
1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。
2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。
3.N=N-1,如果N不为0就重复前面二步,否则排序完成。
## 3.2 冒泡排序代码实现
```
//冒泡排序3
void BubbleSort3(int a[], int n)
{
int j, k;
int flag;
flag = n;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
```
## 3.3 冒泡排序时间复杂度
时间复杂度O(n^2), 空间复杂度O(1), 稳定,因为存在两两比较,不存在跳跃。
排序时间与输入无关,最好,最差,平均都是O(n^2)。数据小时可以作为排序方式。
[1]: http://blog.csdn.net/morewindows/article/details/6709644
[2]: http://images.51cto.com/files/uploadimg/20110826/222536597.jpg
[3]: http://images.51cto.com/files/uploadimg/20110826/222653304.jpg
[4]: http://images.51cto.com/files/uploadimg/20110826/222801489.jpg
近期热议
推荐标签 标签
-
DNSPod
6 引用 • 26 回帖 • 533 关注
DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。
-
996
13 引用 • 200 回帖 • 1 关注
-
GitLab
46 引用 • 72 回帖 • 1 关注
GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。
-
MongoDB
91 引用 • 59 回帖 • 2 关注
MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。
-
GAE
14 引用 • 42 回帖 • 837 关注
Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。
-
RIP
8 引用 • 92 回帖 • 412 关注
愿逝者安息!
-
Pipe
134 引用 • 1128 回帖 • 110 关注
Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。
这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!
-
SpaceVim
3 引用 • 31 回帖 • 115 关注
SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
即用的 Vim-IDE。 -
Hexo
22 引用 • 148 回帖 • 17 关注
Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。
-
思源笔记
26791 引用 • 111671 回帖
思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。
融合块、大纲和双向链接,重构你的思维。
-
负能量
89 引用 • 1251 回帖 • 390 关注
上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)
-
Facebook
4 引用 • 15 回帖 • 444 关注
Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。
-
Access
1 引用 • 3 回帖 • 6 关注
-
PWA
14 引用 • 69 回帖 • 187 关注
PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。
-
书籍
84 引用 • 414 回帖
宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”
-
强迫症
15 引用 • 161 回帖 • 1 关注
强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。
-
Oracle
107 引用 • 127 回帖 • 340 关注
Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。
-
持续集成
15 引用 • 7 回帖 • 3 关注
持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。
-
设计模式
201 引用 • 120 回帖 • 2 关注
设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。
-
FFmpeg
23 引用 • 32 回帖 • 2 关注
FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。
-
VirtualBox
10 引用 • 2 回帖 • 14 关注
VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。
-
PHP
167 引用 • 408 回帖 • 483 关注
PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。
-
Sphinx
1 引用 • 226 关注
Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。
-
Sandbox
443 引用 • 1238 回帖 • 601 关注
如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。
-
JavaScript
730 引用 • 1284 回帖
JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。
-
wolai
2 引用 • 14 回帖 • 3 关注
我来 wolai:不仅仅是未来的云端笔记!
-
酷鸟浏览器
3 引用 • 59 回帖 • 60 关注
安全 · 稳定 · 快速
为跨境从业人员提供专业的跨境浏览器
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于