# 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
近期热议
推荐标签 标签
-
Spark
74 引用 • 46 回帖 • 561 关注
Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。
-
Dubbo
60 引用 • 82 回帖 • 609 关注
Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。
-
IDEA
180 引用 • 400 回帖 • 1 关注
IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。
-
Eclipse
75 引用 • 258 回帖 • 634 关注
Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。
-
酷鸟浏览器
3 引用 • 59 回帖 • 29 关注
安全 · 稳定 · 快速
为跨境从业人员提供专业的跨境浏览器 -
Kubernetes
110 引用 • 54 回帖 • 2 关注
Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。
-
Flume
9 引用 • 6 回帖 • 625 关注
Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。
-
脑图
22 引用 • 70 回帖
脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。
-
Log4j
20 引用 • 18 回帖 • 32 关注
Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。
-
VirtualBox
10 引用 • 2 回帖 • 16 关注
VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。
-
webpack
41 引用 • 130 回帖 • 261 关注
webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。
-
分享
246 引用 • 1786 回帖 • 1 关注
有什么新发现就分享给大家吧!
-
TGIF
287 引用 • 4484 回帖 • 666 关注
Thank God It's Friday! 感谢老天,总算到星期五啦!
-
微软
8 引用 • 44 回帖
微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。
-
SMTP
4 引用 • 18 回帖 • 624 关注
SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。
-
前端
247 引用 • 1347 回帖 • 1 关注
前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。
-
生活
230 引用 • 1454 回帖
生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。
-
Electron
15 引用 • 136 回帖 • 13 关注
Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。
-
GraphQL
4 引用 • 3 回帖 • 18 关注
GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。
-
GitLab
46 引用 • 72 回帖
GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。
-
Maven
186 引用 • 318 回帖 • 327 关注
Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。
-
PostgreSQL
22 引用 • 22 回帖
PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。
-
Python
540 引用 • 672 回帖
Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。
-
Swift
36 引用 • 37 回帖 • 527 关注
Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。
-
WebClipper
3 引用 • 9 回帖 • 1 关注
Web Clipper 是一款浏览器剪藏扩展,它可以帮助你把网页内容剪藏到本地。
-
ReactiveX
1 引用 • 2 回帖 • 148 关注
ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。
-
RYMCU
4 引用 • 6 回帖 • 51 关注
RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于