面试常考数据结构与算法

本贴最后更新于 3008 天前,其中的信息可能已经时移世改
# 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
  • 算法
    428 引用 • 254 回帖 • 24 关注
  • 排序
    19 引用 • 16 回帖 • 1 关注
  • int
    12 引用 • 18 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    冒泡排序哈哈

guobing
会当凌绝顶,一览众山小

推荐标签 标签

  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 153 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 585 关注
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    209 引用 • 2031 回帖
  • V2Ray
    1 引用 • 15 回帖
  • JSON

    JSON (JavaScript Object Notation)是一种轻量级的数据交换格式。易于人类阅读和编写。同时也易于机器解析和生成。

    52 引用 • 190 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 18 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 30 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    264 引用 • 665 回帖
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 52 关注
  • CongSec

    本标签主要用于分享网络空间安全专业的学习笔记

    1 引用 • 1 回帖 • 10 关注
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    107 引用 • 295 回帖 • 2 关注
  • jsoup

    jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 482 关注
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    132 引用 • 188 回帖
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 186 关注
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 816 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    565 引用 • 3532 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 2 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 489 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 4 关注
  • 微服务

    微服务架构是一种架构模式,它提倡将单一应用划分成一组小的服务。服务之间互相协调,互相配合,为用户提供最终价值。每个服务运行在独立的进程中。服务于服务之间才用轻量级的通信机制互相沟通。每个服务都围绕着具体业务构建,能够被独立的部署。

    96 引用 • 155 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖 • 2 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    142 引用 • 442 回帖
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 65 回帖 • 453 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    176 引用 • 995 回帖 • 1 关注
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    497 引用 • 1387 回帖 • 294 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 2 关注