折半插入排序
折半插入排序在本质上还是算作插入排序，不同的是比较的次数减少，直接插入排序是从后往前一个个的去比较，而折半插入排序是折中的方式来进行比较，总体的比较次数会比直接插入排序少，代码如下所示：
public void zbInsert() {
int[] A = {1, 2, 3, 4};
int[] B = {2, 4, 5, 6};
int[] C = new int[A.length+B.length];
/*-------------------
将较长的数组copy到新数组前面部分，
类似直接插入，减少插入预判次数------------------
*/
for (int k = 0;k<A.length+B.length;k++){
if (A.length>=B.length){
if (k<A.length)C[k] = A[k];
if (k>=A.length)C[k] = B[k-A.length];
}else {
if (k<B.length)C[k] = B[k];
if (k>=B.length)C[k] = A[k-B.length];
}
}
int j;
for (int i = A.length;i<C.length;i++){
int left = 0;
int right = i-1;
int current = C[i];
while (right>=left){
int mid = (right+left)/2;
if (C[mid]>current)
right = mid-1;
else
left = mid+1;
}
/*------------将比current大的值往后移动一位-------------*/
for (j = i-1;j>=left;j--)
C[j+1] = C[j];
/*---------------在找到的索引位置赋值---------------*/
C[j+1] = current;
}
for (int k = 0;k<C.length;k++)
System.out.print(C[k]+",");
}
小根堆的方式获取丑数
丑数就是因子只包含2,3,5的数，算法如下，PriorityQueue队列内部默认通过小根堆的方式进行排序。
public int method(int n) {
if (n == 1) return 1;
Queue<Integer> choushu = new PriorityQueue<>();
choushu.offer(1);
for (int i = 2; i <= n; i++) {
/*---------------小根堆的方式排序，每次poll都是弹出最小值---------------*/
int flag = choushu.poll();
if (!choushu.contains(flag * 2)) choushu.offer(flag * 2);
if (!choushu.contains(flag * 3)) choushu.offer(flag * 3);
if (!choushu.contains(flag * 5)) choushu.offer(flag * 5);
}
return choushu.poll().intValue();
}
大根堆的方式获取第N个大的值
大根堆跟小根堆正好相反，不过priorityQueue还是提供了参数进行大根堆的方式排序。
public int kthLargestElement(int n, int[] nums) {
// write your code here
PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length, Collections.reverseOrder());
int result = 0;
for (int i = 0; i < nums.length; i++) {
queue.offer(nums[i]);
}
for (int j = 0; j < n; j++)
result = queue.poll();
return result;
}
Queue队列
稍微了解一下关于queue队列的知识
image.png
Queue：基本上，一个队列就是一个先入先出（FIFO）的数据结构
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接口。
Deque(双端队列)
LinkedList：实现了java.util.Queue接口和java.util.AbstractQueue接口，如上图的中Deque,LinkedList是一种双端队列的存储方式
PriorityQueue 和 ConcurrentLinkedQueue(不阻塞队列)
PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。
ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大小,ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。
阻塞队列
java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。
五个队列所提供的各有不同：
* ArrayBlockingQueue ：一个由数组支持的有界队列。
* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。
网友评论