# 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
近期热议
推荐标签 标签
-
Tomcat
162 引用 • 529 回帖 • 3 关注
Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。
-
Access
1 引用 • 3 回帖 • 2 关注
-
MongoDB
90 引用 • 59 回帖 • 7 关注
MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。
-
Bootstrap
18 引用 • 33 回帖 • 650 关注
Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。
-
C
85 引用 • 165 回帖 • 1 关注
C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。
-
Shell
124 引用 • 74 回帖
Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。
-
博客
273 引用 • 2388 回帖
记录并分享人生的经历。
-
互联网
99 引用 • 367 回帖
互联网(Internet),又称网际网络,或音译因特网、英特网。互联网始于 1969 年美国的阿帕网,是网络与网络之间所串连成的庞大网络,这些网络以一组通用的协议相连,形成逻辑上的单一巨大国际网络。
-
CloudFoundry
5 引用 • 18 回帖 • 177 关注
Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。
-
域名
43 引用 • 208 回帖
域名(Domain Name),简称域名、网域,是由一串用点分隔的名字组成的 Internet 上某一台计算机或计算机组的名称,用于在数据传输时标识计算机的电子方位(有时也指地理位置)。
-
etcd
6 引用 • 26 回帖 • 548 关注
etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。
-
NetBeans
78 引用 • 102 回帖 • 702 关注
NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。
-
反馈
126 引用 • 930 回帖 • 270 关注
Communication channel for makers and users.
-
Office
5 引用 • 34 回帖 • 1 关注
Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。
-
Laravel
20 引用 • 23 回帖 • 740 关注
Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。
-
Notion
10 引用 • 76 回帖
Notion - The all-in-one workspace for your notes, tasks, wikis, and databases.
-
JRebel
26 引用 • 78 回帖 • 677 关注
JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。
-
SEO
35 引用 • 200 回帖 • 20 关注
发布对别人有帮助的原创内容是最好的 SEO 方式。
-
RIP
8 引用 • 92 回帖 • 391 关注
愿逝者安息!
-
IDEA
181 引用 • 400 回帖 • 4 关注
IDEA 全称 IntelliJ IDEA,是一款 Java 语言开发的集成环境,在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品,这家公司总部位于捷克共和国的首都布拉格,开发人员以严谨著称的东欧程序员为主。
-
GitLab
46 引用 • 72 回帖 • 2 关注
GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。
-
Bug
76 引用 • 1742 回帖
Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。
-
CodeMirror
2 引用 • 17 回帖 • 158 关注
-
WordPress
66 引用 • 114 回帖 • 196 关注
WordPress 是一个使用 PHP 语言开发的博客平台,用户可以在支持 PHP 和 MySQL 数据库的服务器上架设自己的博客。也可以把 WordPress 当作一个内容管理系统(CMS)来使用。WordPress 是一个免费的开源项目,在 GNU 通用公共许可证(GPLv2)下授权发布。
-
尊园地产
1 引用 • 22 回帖 • 782 关注
昆明尊园房地产经纪有限公司,即:Kunming Zunyuan Property Agency Company Limited(简称“尊园地产”)于 2007 年 6 月开始筹备,2007 年 8 月 18 日正式成立,注册资本 200 万元,公司性质为股份经纪有限公司,主营业务为:代租、代售、代办产权过户、办理银行按揭、担保、抵押、评估等。
-
黑曜石
21 引用 • 204 回帖
黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。
A second brain, for you, forever.
-
ZeroNet
1 引用 • 21 回帖 • 643 关注
ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于