java集合交错排列

数据结构与算法（java)–链表

数据结构与算法（Java）–栈和递归

数据结构与算法（java)–排序算法及查找

数据结构与算法（java)–哈希表

数据结构与算法（Java）–数结构

数据结构与算法（Java）–图结构

数据结构与算法（Java）–常见算法

leetcode hot100

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度O(n)

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)

• 对于不是只有常数的时间复杂度忽略时间频度的系数、低次项常数
• 对于只有常数的时间复杂度，将常数看为1

常数阶 O(1)

无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是O(1)

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用o1)来表示它的时间复杂度。

对数阶O(log2n)

线性阶O(n)

这其中，循环体中的代码会执行n次，消耗的时间是随着n的变化而变化，时间复杂度为O(n)

线性对数阶O(nlog2n)

此处外部为一个循环，循环了n次。内部也是一个循环，但内部f循环的时间复杂度是log2n
将时间复杂度为O(logn)的代码循环N遍的活，那么它的时间复杂度就是n*O(logN)，即O(nlog2n)

平方阶O(n2)

如果把o(n)的代码再嵌套循环一遍，它的时间复杂度就是o(n2)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(nn),
即o(n2)如果将其中一层循环的n改成m，那它的时间复杂度就变成了O(mn)

立方阶O(n3)

可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的

比较相邻的两个元素，如果第一个比第二个大就交换，重复比较至最后一个元素，这样最后一个便是最大的；然后继续这样比较（除了每一轮比较出来的最后一个；即数组长度len-i-1（第几轮）

代码实现

1. 从第一个元素开始比较，找到最小（大）的之后放入有序区（刚开始全是无序区），然后从无序区的第一个在开始上述比较，得到最小的，放入有序区
2. 一共需要遍历元素个数-1次，当找到第二大（小）的元素时，可以停止。这时最后一个元素必是最大（小）元素。
   代码实现

将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
取出下一个元素，在已经排序的元素序列从后向前扫描；如果该（已排序）元素大于新元素（即取出来的元素），则向后移一位，继续重复比较，直到找到已排序的元素小于等于新元素（稳定排序，不改变原有顺序），将新元素插入该位置；重复上述步骤

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

步骤1：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

步骤2：按增量序列个数k，对序列进行k 趟排序；

步骤3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

冒泡排序的改进。
分区：先在序列中以第一个数作为基准数，将基准数移动到序列的中间某个位置，数的左边的都小于它，右边的都大于它（相同的数可以到任一边）（用到了双指针）
然后利用递归（类似归并排序的感觉）在对基准数左边和右边的序列进行第一个步骤，直到所有的数都归位（即第一个步骤的完成条件）

把长度为n的输入序列分成两个长度为n/2的子序列；递归拆开至只有一个元素，然后从最短序列开始一次排序、合并；最终合并成为一个有序序列

分而治之—治

将所有元素变成和最多位数一样的位数，不够的补零，然后按照从个位比较，排好序之后再按高一位的比较，一直到最高位，然后便得到一个有序数列。

疑问： 为什么是从低位开始比较，而不是高位；从高位开始为什么最后得到的不是有序数列？
高位的权重低于低位，高位确定之后，低位在已经确定高位的数据中进行排序就会打乱顺序，所以应该先按低位排序

也可以通过将最大数变为String类型，再求得它的长度

堆是具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

一般升序排序采用大顶堆，降序排列使用小顶堆

排序思路

排序算法时间复杂度

相关术语解释：

1. 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
2. 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
3. 内排序：所有排序操作都在内存中完成；
4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5. 时间复杂度： 一个算法执行所耗费的时间。
6. 空间复杂度：运行完一个程序所需内存的大小
7. n: 数据规模
8. k: “桶”的个数
9. In-place: 不占用额外内存
10. Out-place: 占用额外内存

有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】
要求: 如果找到了，就提示找到，并给出下标值。

查找思路：从数组的一个元素出发，一个个地和要查找的值进行比较，如果发现有相同的元素就返回该元素的下标。反之返回-1（未找到）

进行二分查找的数组必须为有序数组

• 设置一个指向中间元素下标的变量mid，mid=(left + right)/2
• 让要查找的元素和数组mid下标的元素进行比较

• 如果查找的元素大于arr[mid]，则left变为mid后面一个元素的下标
• 如果查找的元素小于arr[mid]，则right变为mid前一个元素的下标
• 如果查找的元素等于arr[mid]，则mid就是要查找元素所在的位置

• 什么时候结束递归

• 找到就结束递归
• 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出（说明元素不在该数组中）

{1, 10, 22, 22, 100，123} 当一个有序数组中，有多个相同的数值时，如何将所有的数值 都查找到，比如这里的 22 。这时就需要在找到一个元素后，不要立即返回，而是扫描其左边和右边的元素，将所有相同元素的下标保存到一个数组中，然后一起返回

在二分查找中，如果我们要找的元素位于数组的最前端或者最后段，这时的查找效率是很低的。所以在二分查找基础上，引入了插值查找，也是一种基于有序数组的查找方式
插值查找与二分查找的区别是：插值查找每次从自适应 mid 处开始查找。

mid的值在两种查找算法中的求法：

• 二分查找：mid = (left + right)/2
• 插值查找：
  mid = left + (right - left) * (num - arr[left]) / (arr[right] - arr[left])

• 其中num为要查找的那个值