文档章节

程序员必知8大排序3大查找(一)

SuShine
 SuShine
发布于 2015/06/25 15:27
字数 1164
阅读 12
收藏 0

阿里云携手百名商业领袖、技术大咖,带您一探行进中的数字新基建!>>>

第二篇《程序员必知8大排序3大查找(二)》

《程序员必知8大排序3大查找(三)》

每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不扎实,就像是在云里雾里行走一样,只能看到眼前,不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理,要想真正的学习技术还是走下云端,扎扎实实的把基础知识学好,有了这些基础,要掌握那些新技术也就很容易了。

 

要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么对程序的性能进行优化?废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!


1、直接插入排序

 

1)基本思想:在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排

好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数

也是排好顺序的。如此反复循环,直到全部排好顺序。

2)实例


 

2、希尔排序(也称最小增量排序)


1)基本思想:算法先将要排序的一组数按某个增量dn/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。

2)实例:



3、简单选择排序


1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;

然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

2)实例:



4、堆排序


1)基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。

堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

2)实例:

初始序列:46,79,56,38,40,84

建堆:


交换,从堆中踢出最大数


剩余结点再建堆,再交换踢出最大数


依次类推:最后堆中剩余的最后两个结点交换,踢出一个,排序完成。

 

5、冒泡排序


1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

2)实例:



未完待续,第二篇将介绍剩余3大排序,排序稳定性,复杂度(这句话过期,呵呵!)


第二篇杀到,《程序员必知8大排序3大查找(二)》

希望大家多多支持!

本文转载自:http://blog.csdn.net/sfshine/article/details/8764215

SuShine
粉丝 132
博文 630
码字总数 160326
作品 0
朝阳
后端工程师
私信 提问
加载中

评论(0)

程序员:你可以不用,但不能没有!

在各大互联网公司高价抢夺数据人才的环境下,为谋求长期发展、获得高薪,很多人转行到了大数据领域。这条路人才虽缺,但要成为优秀大数据工程师并不轻松:别的不说,光学习新技术,巩固旧知识...

程序员大咖
04/29
0
0
今年面试通关太难,程序员怎么高效提升竞争力?

在各大互联网公司高价抢夺数据人才的环境下,为谋求长期发展、获得高薪,很多人转行到了大数据领域。这条路人才虽缺,但要成为优秀大数据工程师并不轻松:别的不说,光学习新技术,巩固旧知识...

chenssy
04/27
0
0
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集

本文将覆盖 + + + 方面的面试算法题,文中我将给出: 面试中的题目 解题的思路 特定问题的技巧和注意事项 考察的知识点及其概念 详细的代码和解析在开始之前,我们先看下会有哪些重点内容: ...

osc_yiec7bem
04/16
3
0
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
405
7
JAVA基础学习总结(算法篇)

1、排序算法 关于排序算法我就不一一赘述了,建议看下这篇博客,讲的很详细。http://blog.csdn.net/hguisu/article/details/7776068 常用的排序一般是冒泡排序和快速排序。 冒泡排序的基本思...

tomcater
2016/04/13
132
0

没有更多内容

加载失败,请刷新页面

加载更多

Apache Jmeter 入门

Jmeter是一款优秀的开源测试工具, 是每个资深测试工程师,必须掌握的测试工具,熟练使用Jmeter能大大提高工作效率。 本文将通过一个实际的测试例子, 来讲解Jmeter的基本用法。 Jmeter 介绍...

JEECG开源社区
35分钟前
21
0
Spring Cloud 系列之 Apollo 配置中心(二)

本篇文章为系列文章,未读第一集的同学请猛戳这里:Spring Cloud 系列之 Apollo 配置中心(一) 本篇文章讲解 Apollo 部门管理、用户管理、配置管理、集群管理。      点击链接观看:Apo...

哈喽沃德先生
37分钟前
20
0
原生ES-Module

首先是各大浏览器从何时开始支持module的: Safari 10.1 Chrome 61 Firefox 54 (有可能需要你在about:config页面设置启用dom.moduleScripts.enabled) Edge 16 使用方式 首先在使用上,唯一的...

东东笔记
37分钟前
10
0
DevExpress Winforms使用技巧与窍门集合(2020年5月汇总)

下载DevExpress v20.1完整版 DevExpress Winforms Controls 内置140多个UI控件和库,完美构建流畅、美观且易于使用的应用程序。想要体验?点击下载>> 本文中包含一些示例和调整WinForms UI组...

FILA6666
39分钟前
18
0
SwitchGlass for mac 1.4(331) 系统应用快速启动

mac系统应用怎么才能快速启动?这时候你需要一款mac系统应用快速启动软件!SwitchGlass Mac版是Mac电脑上的一款系统应用快速启动工具。SwitchGlass Mac版为你的Mac应用增加了一个专用的应用程...

麦克W
42分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部