数据结构与算法——桶排序

算法简介

桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,适用于待排序数据值域较大但分布比较均匀的情况。工作的原理是将数组元素分到有限数量的桶里,每个桶再各自排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是比较排序,他不受到O(n log n)下限的影响。

桶排序的思想近乎彻底的分治思想。它是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

img

桶排序假设待排序的一组数均匀独立的分布在一个范围中,并将这一范围划分成几个子范围(桶)。然后基于某种映射函数f ,将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ,那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 …

read more

数据结构与算法——基数排序

算法介绍

基数排序(英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序是稳定性的排序。

基数排序和桶排序、计数排序算法一样,都属于非比较型排序算法,且都利用了桶的概念,但对桶的使用方法上有明显差异:

  • 基数排序:根据键值的每位数字来分配桶;
  • 计数排序:每个桶只存储单一键值;
  • 桶排序:每个桶存储一定范围的数值;

冒泡、选择、插入、归并、希尔、堆、快速排序都是基于比较的排序,平均时间复杂度最低O(nlogn);

计数排序、桶排序、基数排序不是基于比较的排序,使用空间换时间,某些时候,平均时间复杂度可以低于O(nlogn)。

它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列 …

read more

数据结构与算法——计数排序

算法介绍

计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组C ,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

img

我们使用下面的例子进行说明。

假设有20个随机整数,其取值范围在0~10之间,对其进行排序,由于这20个随机整数的取值范围是固定的,那么我们可以定义一个长度为11的数组,数组下标为从0到10,并且元素初始值全为0,然后遍历要排序的20个随机整数,将遍历到的数值对应的数组下标进行+1,直到遍历结束。如下图所示:

假设我们要遍历的20个随机数为 …

read more

数据结构与算法——堆排序

算法介绍

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

  • 父节点i的左子节点在位置{\displaystyle (2i+1)};
  • 父节点i的右子节点在位置{\displaystyle (2i+2)};
  • 子节点i的父节点在位置{\displaystyle floor((i-1)/2)};

在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

  • 最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(Build Max Heap):将堆中的所有数据重新排序
  • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

算法步骤 …

read more

数据结构与算法——快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn …

read more

算法介绍

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归:它从树的顶端开始,然后向下操作,每次操作都问同样的问题(我需要做什么来排序这个数组?)并回答它(分成两个子数组,进行递归调用,合并结果),直到我们到达树的底部。

Picture2.png

  • 自下而上的迭代:不需要递归。它直接从树的底部开始,然后通过遍历这些片段再将它们合并起来。

Picture1.png

在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep …

read more

算法原理

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

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

排序步骤

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

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

动图演示

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

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