1、插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。...插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。...将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。...归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上...1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。...值排序 根据map的key值将map进行排序是一个很常用的操作。...值排序 第一种方法也是将map转换成一个list,然后根据value排序,方法与key的排序是一样的。...5 初始化一个静态的不可变的Map 如果你需要一个map像静态常量那样保持不变,那么我们将它复制到一个immutable的map中,也就是不可变Map。...为了创建一个不可变的map,我们需要static修饰符,同时需要一个额外的匿名类,并且在最后一步将其复制到一个不可以操作的map中。
一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。...算法并非容器类型的成员函数,而是一些全局函数,要与迭代器一起搭配使用。 算法的优势在于只需实作一份,可以适应所有的容器,不必为每一种容器量订制。也可以与用户定义的容器搭配。...算法尾词: _if 比如find(按某个值来查找),find_if(按某个条件来查找) _copy 这个尾词用来表示在算法中,元素不光被操作,还会被复制到目标区间。...2、变动性算法,要么直接改变元素值,要么就是在复制到另一个区间的过程中改变元素值。如果是第二种情况,原区间不会发生变化 ? 3、移除性算法是一种特殊的变动性算法。...移除性算法也可以在复制的过程中执行移除。注意,目标区间不能是关联式容器。 ? 4、变序性算法改变元素次序,但不改变元素值。这些算法不能用于关联式容器,因为关联式容器中,元素有固定的次序。 ?
常说的排序都是指内部排序,而不是外部排序。 内部排序的分类 可以分为如下几类: 选择排序 交换排序 插入排序 归并排序 桶式排序 基数排序 上面这些内部排序方法人致有如下图所示的分类。 ?...归并排序 归并的基本思想是将两个(或以上〕有序的序列合并成一个新的有序序列。当然,此处介绍的归并排序主要是将两个有序的数据序列合并成一个新的有序序列。...那么,如何将两个有序的数据序列合并成一个新的有序序列?合并算法的具体步骤如下。 定义变量i,i从0开始,依次等于A序列中每个元素的索引。...定义变量j,j从0开始,依次等于B序列中每个元素的索引 拿A序列中i索引处的元素和B序列中j索引处的元素进行比较,将较小的复制到一 个临时数组中。...不断地重复上面四个步骤,即可将A、B两个序列中的数据元素复制到临时数组中,直到其中一个数组中的所有元素都被复制到临时数组中.最后,将另一个数组中多出来的元素全部复制到临时数组中,合并即完成,再将临时数组中的数据复制回去即可
采用双指针(头尾两端)遍历,从左往右找到比基准值大的第一个数,从右往左找到比基准值小的第一个数,交换两数位置,直到头尾指针相等或头指针大于尾指针,把基准值与头指针的数交换。...交换头尾值,尾指针索引减一,固定最大值。 重新构建大顶堆。 重复步骤2~3,直到最后一个元素,排序完成。 构建大顶堆的思路,可以看代码注释。 动画演示: ?...break; } //如果不是大根堆,则交换父节点的值 swap(nums, largestIndex, index);...根据数组的长度,创建出若干个桶。 遍历数组的元素,根据元素的值放入到对应的桶中。 对每个桶的元素进行排序(可使用快排,插入排序等)。 按顺序合并每个桶的元素,排序完成。...对于数组中的元素分布均匀的情况,排序效率较高。相反的,如果分布不均匀,则会导致大部分的数落入到同一个桶中,使效率降低。 动画演示(来源于五分钟学算法,侵删): ?
Java 集合类主要存放于 Java.util 包中,大致可以分为两大体系(一个是 Collection,另一个是 Map)、三/四种类型(List 列表、Queue 队列、Set 集合、Map 映射)...如果 equals 为 false 就不是同一个元素。哈希值相同 equals 为 false 的元素是怎么存储呢,就是在同样的哈希值下顺延(可以认为哈希值相同的元素放在一个哈希桶中)。...void sort(List list, Comparator c) 自定义排序,由Comparator来制定排序的逻辑 void swap(List list, int i , int j) 交换指定索引位置的元素...3、关于 Java Iterator(迭代器) Java Iterator(迭代器)不是一个集合,它是一种用于访问集合的方法,可用于迭代 ArrayList 和 HashSet 等集合。...调用 it.next() 会返回迭代器的下一个元素,并且更新迭代器的状态。 调用 it.hasNext() 用于检测集合中是否还有元素。 调用 it.remove() 将迭代器返回的元素删除。
则应使用基于时间的索引以便更轻松地维护索引。 如果写入数据流的吞吐量随时间而变化,则需要适当地改变下一个索引的配置才能实现数据的动态扩展。 那么,如何查询分散到不同的基于时间索引的所有文档?...在Elasticsearch中创建新索引时,可以配置每个分片中的分段的排序方式。 默认情况下,Lucene不会应用任何排序。...它可能导致垃圾收集持续数分钟而不是毫秒,并且可能导致节点响应缓慢甚至断开与集群的连接。 在Elasticsearch分布式系统中,让操作系统终止节点更有效。...: 集群中临时重启、剔除一个节点; 集群逐个升级节点;当您关闭节点时,分配过程将立即尝试将该节点上的分片复制到集群中的其他节点,从而导致大量浪费的IO....提高多个字段的搜索速度的常用技术是在索引时将其值复制到单个字段中。 对于经常查询的某些字段,请使用Elasticsearch的copy-to功能。
1、插入排序 描述: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。...插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。...将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。...归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上...1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
寻找二叉树的公共父节点 51. 通过寻找两条路径,然后寻找最后一个公共节点。 52. SVM 核函数,合并两个文件的问题 53. b+ b - 树、红黑树、要求写出排序算法 54....实操: 为了反转这个单链表,我们先让头结点的 next 域指向结点 2,再让结点 1 的 next 域指向结点 3,最后将结点 2 的 next 域指向结点 1,就完成了第一次交换,顺序就变成了 Header...空间复杂度:快排是 O(n) 归并是 O(2n). 40. http://t.cn/zlZWjUl 41. args 是 Java 命令行参数,我们在 DOS 中执行 Java 程序的时候使用 “java...当然也可以在一个类中 main 方法中直接调用另一个类里的 main 方法,因为 main 方法都是 static 修饰的静态方法,因此可以通过类名. main 来调用,这时就可在调用处 main 方法中传入...实操 60.LDA 提取特征,再用 SVM 做分类 61.62.63. 实操 64.a1 与 a2 值相等,排序完以后两者顺序仍然没变则是稳定排序,稳定排序有插入、冒泡、归并 65.
开始i在左边序列的第一个位置,j在右边序列的第一个位置,然后就是寻找左右两个序列中的最小值,放到新序列中,这时可能会出现一边的元素都放置完毕了,而另外一边还存在元素,此时只需将剩余的元素按顺序放进新序列即可...,因为这时左右两边的序列已经是有序的了,最后将新序列复制到旧序列。...这里也特别需要注意,因为合并的过程是分步的,而并非一次合并完成,所以数组的索引是在不断变化的。 ?...拿到的第一个元素为53,其个位数为3,所以将53放入编号为3的桶中,第二个元素3的个位数也是3,所以也放在编号为3的桶中,而第三个元素542的个位数为2,所以将542放入编号为2的桶中,以此类推。...(RadixSortDemo.java:22) 结果为堆内存溢出,所以在对大量数据进行排序的时候,基数排序显然不是一个好的选择,因为提升排序效率的条件是牺牲大量的内存空间,当数据足够多时,内存空间就不够用了
,其意思是将排序串拆分成最小的单位之后,再一个个合并成有序的子串。...按着上述的步骤继续不断重复步骤 2 的内容,我们会看到子串 2 首先到末尾。此时子串 1 还剩下一些数值,这些数值肯定是更大的值,那么直接将这些数值复制到 temp 数组中即可。...选择排序是每次选出最值,然后放到数组头部。而冒泡排序则是不断地两两对比,将最值放到数组尾部。本质上,他俩每次都是选出最值,然后放到一边。...其最大的不同点是:选择排序只需要做一次交换,而冒泡排序则需要两两对比交换,所以冒泡排序的效率相对来说会低一些,因为会做多一些无意义的交换操作。 快速排序与归并排序的区别?...刚刚看了一下,快速排序和归并排序,我觉得差别可以提现在拆分合并的过程中,比较的时机。 快排和归并,都是不断拆分到最细。但是归并更纯粹,拆分时不做比较,直接拆!而快排还是会比较一下的。
前言所学 前面我们学习了归并,希尔俩个排序,下面由这张图来总结一下八大排序 可能有的小伙伴会说,学这些排序有什么用,平时开发也用不到,但是我的理解是这样的: 锻炼思维,排序中蕴含的思维很多,双指针...,递归,分治等等 普及常识性问题 面试,区分人才 堆排序 堆的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆 大顶堆,小顶堆...交换头尾值,尾指针索引减一,固定最大值。 重新构建大顶堆。 重复步骤2,3直到最后一个元素排序完成。...过程 排序过程: (1)设置一个定量的数组当作空桶子; (2)寻访序列,并且把记录一个一个放到对应的桶子去; (3)对每个不是空的桶子进行排序。...(4)从不是空的桶子里把项目再放回原来的序列中。
空间复杂度 快速排序在每次分割的过程中,需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N 次的分割处理,所以占用空间也是 Nlog2N 个。...算法稳定性 在快速排序中,相等元素可能会因为分区而交换顺序,所以它是不稳定的算法。...已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…),该序列的项来自这两个算式。 这项研究也表明“比较在希尔排序中是最主要的操作,而不是交换。”...算法思想 从待排序序列中,找到关键字最小的元素; 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换; 从余下的 N - 1 个元素中,找出关键字最小的元素,重复 1、2 步,直到排序结束。...每次从两个段中取出一个记录进行关键字的比较,将较小者放入 R2 中。最后将各段中余下的部分直接复制到 R2 中。
我遇到过那些人那些事,还有,我希望遇见你 点击上方蓝字“在北方玩弹子球”一起玩耍 插入排序 基本思想:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。...maxHeapDown(a, 0, i-1); } } /* * 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是...* 其中,N为数组下标索引值,如数组中第1个数对应的N为0。...也就是将一个很多数据的数组分成前后两部分,然后不断递归归并排序,再合并,最后返回有序的数组。...当i在j的左边时,将i右移,移过哪些小于枢纽元的元素,并将j左移,已过那些大于枢纽元的元素,当i和j停止时,i指向一个大元素,而j指向一个小元素,如果i在j的左边,那么将这两个元素交换,其效果是把一个大元素推向右边
其实,堆就是一颗完全二叉树,由上面的知识点回顾可以知道,任意给定一个数组,我们就能将它构造成一颗完全二叉树,也就是创建一个“堆”--ps:还好业内标准称它为一堆,而不是一坨 :) 其中,堆又可以分为最大堆与最小堆...下面该"堆排序"(HeapSort)登场了,其思路为: 1、先将给定待排序的数组通过一定处理,形成一个“最大堆” 2、然后将根节点(root)与最后一个序号的节点(lastNode)对换,这样值最大的根节点...6、归并排序算法(MergeSort) 思路:将数组中的每个元素看作一个小序列,然后二二合并成一个有序的新序列(这样序列个数从N变成了N/2,但是每个小序列的长度从1变成2),然后继续将这些新序列二二合并...此时,可以提取关键码建立索引表,然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表,排序前令t[i]=i,1≤i≤n。...若排序算法中要求交换记录 R[i]和 R[j],则只须交换 t[i]和 t[j]即可。排序结束后,数组 t[n]就存放了记录之间的顺序关系
java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化,就像一个工具类,服务于Java的Collection框架。...,然后就是将list转换成一个数组,再对这个数组进行排序,排序完之后,再利用iterator重新改变list。...> list,int i,int j) 在指定列表的指定位置处交换元素。 参数:list-进行元素交换的列表,i-要交换的一个元素的索引,j-要交换的另一个元素的索引。...extends T> src) 将所有元素从一个列表复制到另一个列表。执行此操作后,目标列表中每个已复制元素的索引将等同于源列表中该元素的索引,目标列表的长度至少必须等于源列表。 ...7.7、替换所有函数replaceAll() 函数定义:public static boolean replaceAll(List list,T oldVal,T newVal) 使用另一个值替换列表总出现的所有的某一指定值
再如,快速排序原本是不稳定的排序方法,但若待排序记录中只有一组具有相同关键码的记录,而选择的轴值恰好是这组相同关键码中的一个,此时的快速排序就是稳定的。...(递归合并) 思路:拆拆拆到单个数字,合并合并合并 归并排序是采用分治法的一个非常典型的应用。...然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。...:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1 当k不是很大时,这是一个很有效的线性排序算法。...则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序。
求中值元素,中值不是平均值,而是排序后中间那个元素的值,同样,数据量可能很大,甚至源源不断到来。 堆还可以实现排序,称之为堆排序,不过有比它更好的排序算法,所以,我们就不介绍其在排序中的应用了。...而下面的这几个则都不是完全二叉树: ? 编号与数组存储 在完全二叉树中,可以给每个节点一个编号,编号从1开始连续递增,从上到下,从左到右,如下图所示: ?...它使得逻辑概念上的二叉树可以方便的存储到数组中,数组中的元素索引就对应节点的编号,树中的父子关系通过其索引关系隐含维持,不需要单独保持。比如说,上图中的逻辑二叉树,保存到数组中,其结构为: ?...与排序二叉树不同,在堆中,可以有重复元素,元素间不是完全有序的,但对于父子节点之间,有一定的顺序要求,根据顺序分为两种堆,一种是最大堆,另一种是最小堆。 最大堆是指,每个节点都不大于其父节点。...堆是一种比较神奇的数据结构,概念上是树,存储为数组,父子有特殊顺序,根是最大值/最小值,构建/添加/删除效率都很高,可以高效解决很多问题。 但在Java中,堆到底是如何实现的呢?
领取专属 10元无门槛券
手把手带您无忧上云