2020-3-30 算法1

写的比较简略

排序

冒泡排序

没啥好说的，依次将剩余的数中最小的移到前面。

插入排序

将数依次与前一个比较，小的交换位置，若没有，停止。

a[] `待排序数组`
N = a.lenth()
for i in range(N):
  j = i
  while (j > 0 && less(a[j], a[j-1]) ) {
    exch(a,j,j-1)
    j--
  }

希尔排序

选取一个量度，以此为量度将剩余数字依次以量度向前比较交换移动，最后直到量度为1

N = a.lenth()
h = 1
while h < N/3:
  h = 3*h + 1
while h > 1:
  i = h
  for i in range(N):
    j = i
    while (j >= h && less(a[j], a[j-h]) ):
      exch(a,j,j-h)
      j = -h
  h = h/3

归并排序

将两部分已经排好序的内容合并为一个有序的数组

# a[lo...mid],a[mid+1...hi]
i = lo
j = mid + 1
aux = a
for k in range(hi):
  if i>mid:
    a[k] = aux[j++]
  else if j>hi:
    a[k] = aux[i++]
  else if (less(aux[i],aux[j])):
    a[k] = aux[i++]
  else a[k] = aux[j++]

自底向上的归并排序

从小的依次到大的归并排序

def sort(a,lo,hi):
  if hi<=lo:
    return
  int mid = lo + (hi-lo)/2
  sort(a,lo,mid)
  sort(a,mid+1,hi)
  merge(a,lo,mid,hi)#归并排序

sort(a,0,a.lenth()-1)

红黑树

参考教程
AVL数或是红黑树 都能实现高速查询，有差别是 红黑树达到了以O(log2 n)的时间复杂度进行搜索、插入、删除操作，比较平衡

概念

• VAL是二叉平衡树，任何节点子树的高度都≤1
• 红黑树有几个特性：
  1，节点红或者黑 2，根节点黑 3，叶节点（NIL）黑 4，红节点两子节点黑 5，任意节点到叶子节点包含相同数量的黑节点

变化

为了达到自平衡，红黑树有三种变化方式：左旋，右旋，变色

插入删除

插入都是红色节点，首先进行查找，查询到位置，然后插入后观察是否自平衡。这里就直接使用参考里面的图。删除同理。


虽然插入删除非常复杂，但是进行查询内容就很快，方便。