算法 & 数据结构

• 耗时与输入无关(即使集合已经排序过, 仍然会消耗同样的时间, 因为总是要遍历剩余的所有元素)
• 原地排序(最左侧是已经排序的集合)

• 在小数组情况下优于冒泡和选择排序
• 原地排序(最左侧是已经排序的集合)

• 即使是排序大型数组, 性能也可接受(尽管还是慢于能在生产中使用的排序算法)

// 来自: 维基百科
public static void shellSort(int[] arr) {
	int length = arr.length;
	int temp;
	for (int step = length / 2; step >= 1; step /= 2) {
		for (int i = step; i < length; i++) {
			temp = arr[i];
			int j = i - step;
			while (j >= 0 && arr[j] > temp) {
				arr[j + step] = arr[j];
				j -= step;
			}
			arr[j + step] = temp;
		}
	}
}

• 自顶向下的归并排序 TopDownMergeSort (递归): 将大数组分割成小数组, 递归这一过程, 最终完成归并.
• 自底向上的归并排序 BottomUpMergeSort (循序渐进):
  从元素数量为2的小数组开始排序,
  完成一遍之后再从头开始排序元素数量为4的数组(上一轮的两个小数组), 以此类推, 最后完成最大数组的排序.
  此方法比较适合链表结构.

• 分而治之

• 归并排序的数组拆分先于数组内容, 总是从中间拆分.
  快速排序的数组拆分后于数组内容, 拆分的位置取决于数组的内容.
• 虽然归并排序的算法复杂度稳定为O(nlogn), 但归并排序的速度慢于快速排序.
  若将算法复杂度误认为算法的速度, 就会被误导.

• 分而治之
• 可原地排序
• 高性能

• 前序/先序(preorder)
• 中序(inorder, 在二叉树中出现),
• 后序(postorder)

• 前序/先序: 在递归后代之前调用回调
• 中序(二叉树): 递归left, 调用回调, 递归right
• 后序: 在递归后代之后调用回调

1. 1.
   限制深度优先搜索的深度, 初始值为1, 开始DFS, 但在DFS达到限制深度时就返回.
2. 2.
   如果找到目标节点, 则结束算法.
   如果未能找到目标节点, 则将深度限制加1, 再次执行步骤1.

• 使用次数最多的项目, 即使长时间不使用, 也不会被删除.
• 刚刚进入缓存的项目, 很容易成为使用计数值最小的项目.

• 空序列.
• A, B, C, D.
• AB, AC, AD, BC, BD, CD.
• ABC, ABD, ACD, BCD.
• ABCD.

• https://zschuessler.github.io/DeltaE/learn/
• http://www.easyrgb.com/en/math.php
• https://en.wikipedia.org/wiki/Color_difference

1. 1.
   将图片中的每个像素按照RGB颜色放进三维空间.
2. 2.
   将三维空间平均切分为27个桶(即3x3x3切割).
3. 3.
   将落在同一个桶中的像素的颜色值平均, 得到该桶的颜色值.
4. 4.
   将桶按其中的像素数量进行降序排序, 即可得到色板.

1. 1.
   设定色板的颜色数量.
2. 2.
   将图片中的所有像素放进一个桶内.
3. 3.
   统计桶中所有像素的颜色值, 找到RGB三个通道中数值范围最大的通道, 将该通道的数值范围视作这个桶的颜色范围.
4. 4.
   找到颜色范围最大的桶, 根据其数值范围最大的通道的值对像素排序.
5. 5.
   执行"中位切割": 将桶等分为"中位前"和"中位后"两个.
6. 6.
   对得到的新桶重复执行步骤3~5, 直到桶的数量与要求的色板颜色数量相同.
7. 7.
   对每个桶中的像素的颜色值执行平均, 得到调色盘.

require! 'prelude-ls': {round, map, zip-with}
nearest-neighbor-interpolation = (zoom, src-image) ->
  color = (image, x, y) ->
    i = (y * image.width + x) * 4
    map (|| 0), image.data[i to i + 3]
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image= ctx.create-image-data canvas.width, canvas.height
  for dst-x from 0 til canvas.width
    for dst-y from 0 til canvas.height
      src-color = color src-image, (round dst-x / zoom), (round dst-y / zoom)
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-color = map (/ 2), zip-with (+), src-color, color dst-image, dst-x, dst-y
      for i from 0 to 3
        dst-image.data[dst-i + i] = dst-color[i]
  ctx.put-image-data dst-image, 0, 0
  canvas

require! 'prelude-ls': {map, round, floor, ceiling, sqrt, abs, sum}
bilinear-interpolation-put = (zoom, src-image) ->
  color = (image, offset, point) -->
    if point.x >= image.width or point.y >= image.height
      if offset is 3
        255
      else
        0
    else
      image.data[(image.width * point.y + point.x) * 4 + offset]
  [R, G, B, A] = map (color src-image), [0 to 3]
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image = ctx.create-image-data canvas.width, canvas.height
  for dst-x from 0 til canvas.width
    for dst-y from 0 til canvas.height
      src = x: dst-x / zoom, y: dst-y / zoom
      lt = x: floor(src.x), y: floor src.y
      rt = x: ceiling(src.x), y: floor src.y
      lb = x: floor(src.x), y: ceiling src.y
      rb = x: ceiling(src.x), y: ceiling src.y
      weight-mean = (src, points) ->
        weights = []
        sf = []
        for p, i in points when p.x < src-image.width and p.y < src-image.height
          w = sqrt(abs(p.x - src.x) * abs(p.y - src.y))
          w = 1 / w if w isnt 0
          weights.push w
          sf.push ((w, p)->
            (f) ->
              w * f p
          )(w, p)
        (f) ->
          s = sum map ((s) -> s(f)), sf
          if sum(weights) is 0 then 0 else s / sum weights
      get-weight-mean = weight-mean src, [lt, rt, lb, rb]
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-image.data[dst-i + 0] = round get-weight-mean R
      dst-image.data[dst-i + 1] = round get-weight-mean G
      dst-image.data[dst-i + 2] = round get-weight-mean B
      dst-image.data[dst-i + 3] = round get-weight-mean A
  ctx.put-image-data dst-image, 0, 0
  canvas

require! 'prelude-ls': {map, floor}
bicubic-interpolation-put = (zoom, src-image)->
  color = (image, x, y) ->
    i = (y * image.width + x) * 4
    map (|| 0), image.data[i to i + 3]
  triangle-interpolation = f ->
    f = f / 2
    if f < 0
      f + 1
    else
      1 - f
  clamp = value ->
    return 255 if value > 255
    return 0 if value < 0
    value
  canvas = document.create-element \canvas
  canvas.width = src-image.width * zoom
  canvas.height = src-image.height * zoom
  ctx = canvas.get-context \2d
  dst-image = ctx.create-image-data canvas.width, canvas.height
  for dst-y from 0 til dst-image.height
    src-y = dst-y * zoom
    j = floor src-y
    t = src-y - j
    for dst-x from 0 til dst-image.width
      src-x = dst-x * zoom
      k = floor src-x
      u = src-x - k
      rgba = [0, 0, 0, 0]
      s = 0
      for m from -1 til 3
        for n from -1 til 3
          rgb = color src-image, j + m, k + n
          f1  = triangle-interpolation m - t
          f2 = triangle-interpolation -(n - u)
          s += f2 * f1
          rgba[0] += rgb[0] * f2 * f1
          rgba[1] += rgb[1] * f2 * f1
          rgba[2] += rgb[2] * f2 * f1
          rgba[3] += rgb[3] * f2 * f1
      dst-i = (dst-y * canvas.width + dst-x) * 4
      dst-image.data[dst-i + 0] = clamp parseInt rgba[0] / s
      dst-image.data[dst-i + 1] = clamp parseInt rgba[1] / s
      dst-image.data[dst-i + 2] = clamp parseInt rgba[2] / s
      dst-image.data[dst-i + 3] = clamp parseInt rgba[3] / s
  ctx.put-image-data dst-image, 0, 0
  canvas

• 对已经走过的节点重复访问.
• 递归过深可能导致栈溢出.

• 如果当前像素只与一方连通: 将当前像素设置为连通方的标记.
• 如果当前像素与双方都连通:
  将当前像素设置为其中一方的标记.
  如果双方的标记不同, 则记录下双方标记的等价关系, 供之后使用.
• 如果当前像素与双方都不连通: 为当前像素分配一个新的标记.

1. 1.
   随机生成初始种群.
2. 2.
   评估种群中个体的适应度, 淘汰掉适应度低的个体(模拟自然选择).
3. 3.
   对留存下来的个体进行某种操作(交叉crossover, 突变mutation等)来产生不同基因的子代.
4. 4.
   回到步骤2.

/**
 ,* @param a a <= b
 ,* @param b b >= a
 ,* @param alpha [0, 1]
 ,*/
function mix(a: number, b: number, alpha: number): number {
  return a * (1 - alpha)
       + b * alpha
}

• 如果弹出的值是要删除的值, 什么也不做.
• 如果弹出的值不是要删除的值,
  用弹出的值替换掉dense数组和sparse数组里要删除的值.