算法原理

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。(有点像扑克牌在手上排序的过程)

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

排序步骤

将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

动图演示

img

代码实现

public static int[] insert_sort_original(int[] nums) {
    int[] arr = Arrays.copyOf(nums, nums.length);
    int valuationCnt=0;  // 赋值操作计数
    int comparisonCnt=0;  // 比较操作计数
    for (int i …
read more

数据结构与算法——希尔排序

算法原理

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。该方法实质上是一种分组插入方法

希尔排序把元素按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

简单插入排序很循规蹈矩,不管数组分布是怎么样的,依然一步一步的对元素进行比较,移动,插入,比如[5,4,3,2,1,0]这种倒序序列,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序,小的基本在前,大的基本在后。然后缩小增量 …

read more

数据结构与算法——选择排序

排序思想

首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法我们称之为选择排序。选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

img

那如何选出最小的一个元素呢?

很容易想到:先随便选一个元素假设它为最小的元素(默认为无序区间第一个元素),然后让这个元素与无序区间中的每一个元素进行比较,如果遇到比自己小的元素,那更新最小值下标,直到把无序区间遍历完,那最后的最小值就是这个无序区间的最小值。

算法性能

选择排序是不稳定的排序方法。

时间复杂度

选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n(n - 1)/2 次。选择排序的赋值操作介于 0 和 3(n …

read more

数据结构与算法——冒泡排序

定义

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

算法原理

冒泡排序算法的原理如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

算法复杂度是 O(n^2),空间复杂度是常数 O(1)。但可以记录一个不需要交换的位置,把最好情况的时间复杂度降到 O(n)。详细可以参考下文优化部分的实现 …

read more

数据结构与算法——链表

定义

相比数组,链表是一种稍微复杂一点的数据结构。对于两者,我们常常将会放到一块儿来比较。

从图中我们看到,数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。

而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。

链表结构五花八门,主要有三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。

单向链表

我们刚刚讲到,链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。

其中有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址 …

read more

数据结构与算法——数组

定义

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

这个定义里有几个关键词,理解了这几个关键词,我想你就能彻底掌握数组的概念了。

首先是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。

而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据。正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

随机访问

我们拿一个长度为 10 的 int 类型的数组 …

read more

数据结构与算法——复杂度分析

概述

从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。

想要学习数据结构与算法,首先要掌握一个数据结构与算法中最重要的概念——复杂度分析。它几乎占了数据结构和算法这门课的半壁江山,是数据结构和算法学习的精髓。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题,因此,我们就需要一个考量效率和资源消耗的方法,这就是复杂度分析方法。

下图几乎涵盖了所有数据结构和算法书籍中都会讲到的知识点:

但是,作为初学者,或者一个非算法工程师来说,并不需要掌握图里面的所有知识点。下面总结了 20 个最常用的、最基础数据结构与算法,不管是应付面试还是工作需要,其实只要集中精力逐一攻克这 20 个知识点就足够了:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树

  • 10 …

read more

VxLAN协议详解

VxLAN简介

背景

任何技术的产生,都有其特定的时代背景与实际需求,VXLAN正是为了解决云计算时代虚拟化中的一系列问题而产生的一项技术。那么我们先看看 VXLAN 到底要解决哪些问题。

  • 虚拟机规模受网络设备表项规格的限制

对于同网段主机的通信而言,报文通过查询MAC表进行二层转发。服务器虚拟化后,数据中心中VM的数量比原有的物理机发生了数量级的增长,伴随而来的便是虚拟机网卡MAC地址数量的空前增加。一般而言,接入侧二层设备的规格较小,MAC地址表项规模已经无法满足快速增长的VM数量。

  • 传统网络的隔离能力有限

虚拟化(虚拟机和容器)的兴起使得一个数据中心会有动辄上万的机器需要通信,而传统的 VLAN 技术在标准定义中只有12比特,也就只能支持 4096 个网络上限,已经显然满足不了不断扩展的数据中心规模。

  • 虚拟机迁移范围受限

虚拟机迁移,顾名思义,就是将虚拟机从一个物理机迁移到另一个物理机,但是要求在迁移过程中业务不能中断。要做到这一点,需要保证虚拟机迁移前后,其IP地址、MAC地址等参数维持不变。这就决定了,虚拟机迁移必须发生在一个二层域中。而传统数据中心网络的二层域,将虚拟机迁移限制在了一个较小的局部范围内。此外,解决这个问题同时还需保证二层的广播域不会过分扩大,这也是云计算网络的要求。

传统“二层+三层”的网络在应对这些要求时变得力不从心,虽然通过很多改进型的技术比如堆叠、SVF …

read more

深入理解大数据之——事务及其ACID特性

事务简介

事物的定义

事务(Transaction)是由一系列对系统中数据进行访问或更新的操作所组成的一个程序执行逻辑单元(Unit)。在计算机术语中,事务通常就是指数据库事务 。

57355-20190323094924183-1338282146.png

在数据库管理系统(DBMS)中,事务是数据库恢复和并发控制的基本单位。它是一个操作序列,这些操作要么都执行,要么都不执行,它是一个不可分割的工作单位。

例如,银行转帐工作:从源帐号扣款并使目标帐号增款,这两个操作必须要么全部执行,要么都不执行,否则就会出现该笔金额平白消失或出现的情况。所以,应该把他们看成一个事务。

在现代数据库中,事务还可以实现其他一些事情,例如,确保你不能访问别人写了一半的数据;但是基本思想是相同的——事务是用来确保无论发生什么情况,你使用的数据都将处于一个合理的状态

transactions are there to ensure, that no matter what happens, the data you work with will be in …

read more

Flink 词汇表

Flink应用程序集群是指仅执行一个Flink作业专用的Flink集群。该Flink集群的生命周期与对应Flink作业的生命周期相同。在工作模式下,以前的Flink应用程序集群也称为Flink集群。点击查看与Flink Session Cluster的比较。

一种分布式系统,通常由一个Flink Master和一个或多个 Flink TaskManager进程组成。

事件

事件是有关由应用程序建模的域的状态更改的声明。事件可以是流或批处理应用程序的输入和/或输出。事件是特殊类型的记录

执行图

物理图

函数

函数由用户实现,并封装Flink程序的应用程序逻辑。大多数函数由相应的算子包装 。

实例

术语实例用于描述在运行期间特定类型的特定实例(通常是 算子函数)。由于Apache Flink主要是用Java编写的 …

read more

大陆访问Vultr各节点VPS网速测试综合报告

限时福利

Vultr新用户赠送$50活动入口

vultr-promotion

测试方法

采用以下方法:

  • 本地Ping测试
  • 腾讯云主机Ping测试
  • 本地下载测试
  • 腾讯云主机下载测试
  • 站长工具综合测试

节点列表

Location Looking Glass Download Test File: IPv4
Frankfurt, DE fra-de-ping.vultr.com 100MB 1GB
Amsterdam, NL ams-nl-ping.vultr.com 100MB 1GB
Paris, France par-fr-ping.vultr.com 100MB 1GB
London, UK lon-gb-ping.vultr.com 100MB 1GB
Singapore sgp-ping.vultr.com …
read more

Flink DataStream API教程

在本文中,我们将从头开始,介绍从设置Flink项目到在Flink集群上运行流分析程序。

Wikipedia提供了一个IRC频道,其中记录了对Wiki的所有编辑。我们将在Flink中读取此通道,并计算每个用户在给定时间窗口内编辑的字节数。这很容易使用Flink在几分钟内实现,但它将为您提供一个良好的基础,从而开始自己构建更复杂的分析程序。

设置Maven项目

我们将使用Flink Maven Archetype来创建我们的项目结构。有关此内容的更多详细信息,请参阅Java API快速入门。出于我们的目的,运行命令是这样的:

$ mvn archetype:generate \
    -DarchetypeGroupId=org.apache.flink \
    -DarchetypeArtifactId=flink-quickstart-java \
    -DarchetypeVersion=1.8.0 \
    -DgroupId=wiki-edits \
    -DartifactId=wiki-edits \
    -Dversion=0.1 \
    -Dpackage=wikiedits \
    -DinteractiveMode=false

您可以编辑groupIdartifactIdpackage如果你喜欢 …

read more

深入理解大数据之——Lambda架构

传统系统的问题

“我们正在从IT时代走向DT时代(数据时代)。IT和DT之间,不仅仅是技术的变革,更是思想意识的变革,IT主要是为自我服务,用来更好地自我控制和管理,DT则是激活生产力,让别人活得比你好”

——阿里巴巴董事局主席马云。

数据量从M的级别到G的级别到现在T的级、P的级别。数据量的变化数据管理系统(DBMS)和数仓系统(DW)也在悄然的变化着。 传统应用的数据系统架构设计时,应用直接访问数据库系统。当用户访问量增加时,数据库无法支撑日益增长的用户请求的负载时,从而导致数据库服务器无法及时响应用户请求,出现超时的错误。出现这种情况以后,在系统架构上就采用下图的架构,在数据库和应用中间过一层缓冲隔离,缓解数据库的读写压力。

然而,当用户访问量持续增加时,就需要考虑读写分离技术(Master-Slave)架构则如下图,分库分表技术。现在,架构变得越来越复杂了,增加队列、分区、复制等处理逻辑。应用程序需要了解数据库的schema,才能访问到正确的数据。

商业现实已经发生了变化,所以现在更快做出的决定更有价值。除此之外,技术也在不断发展。Kafka,Storm,Trident,Samza …

read more

Flink 分布式运行时环境

Tasks and Operator Chains

对于分布式执行,Flink将多个算子子任务链串联成任务。每个任务由一个线程执行。将算子链接到任务是一项有用的优化:它可以减少线程到线程切换和缓冲的开销,并在降低延迟的同时提高整体吞吐量。可以配置链接行为; 有关详细信息,请参阅链接文档

下图中的示例数据流由五个子任务执行,因此具有五个并行线程。

算子链接到任务

Job Managers, Task Managers, Clients

Flink运行时包含两种类型的进程:

  • JobManagers(也称为masters)协调分布式执行。他们安排任务,协调检查点,协调故障恢复等。

Job Manager总是至少有一个。高可用性设置将具有多个JobManagers,其中一个始终是领导者,其他处于待机状态

  • TaskManagers(也叫workers)执行dataflow的任务(或者更具体地说应该是子任务),以及缓冲和交换data streams

必须始终至少有一个TaskManager。

JobManagers和TaskManagers可以通过多种方式启动:作为独立集群直接在计算机上,在容器中 …

read more

Flink FAQ

Flink是一个非常通用的系统,用于数据处理和数据驱动的应用程序,数据流作为核心构建块。这些数据流可以是实时数据流或存储的历史数据流。例如,在Flink的视图中,文件是存储的字节流。因此,Flink支持实时数据处理和应用程序,以及批处理应用程序。

流可以是无界的(没有结束,事件不断发生)或受限制(流有开始和结束)。例如,来自消息队列的Twitter馈送或事件流通常是无界的流,而来自文件的字节流是有界流。

如果一切都是流,为什么Flink中有DataStream和DataSet API?

有界流通常比无界流更高效。在(近)实时处理无限事件流需要系统能够立即对事件起作用并产生中间结果(通常具有低延迟)。处理有界流通常不需要产生低延迟结果,因为无论如何数据都是旧的(相对而言)。这允许Flink以简单且更高效的方式处理数据。

DataStream API 捕获无界和有界的流的连续处理,以支持低等待时间的结果以及对事件和时间(包括事件时间)灵活反应的模型。

DataSet API 具有加快有界的数据流的处理的技术。将来,社区计划将这些优化与DataStream API中的技术相结合。

Flink如何与Hadoop栈相关联 …

read more

photo-zzz.png

Hao JiangJustin Time

We only live once, and time just goes by.

  • R&D Engineer @H3C
  • Hangzhou, China

  • Facebook
    微博
    Linkedin
    Github
    Email
    Instagram
    ResearchGate
    知乎
    OSChina