回音壁

一切爆发都有片刻的宁静/一切死亡都有冗长的回声

Algotithm

• 分类: python • 标签: algorithm

1冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

时间复杂度：O(n^2) 空间复杂度：O(1)

1
2
3
4
5
6
7
8
def bubble_sort(lists):
  # 冒泡排序
  count = len(lists)
  for i in range(0, count):
    for j in range(i + 1, count):
      if lists[i] > lists[j]:
        lists[i], lists[j] = lists[j], lists[i]
  return lists

2选择排序

基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

时间复杂度：O(n^2) 空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
def select_sort(lists):
  # 选择排序
  count = len(lists)
  for i in range(0, count):
    min = i
    for j in range(i + 1, count):
      if lists[min] > lists[j]:
        min = j
    lists[min], lists[i] = lists[i], lists[min]
  return lists

3插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据,

时间复杂度：O(n^2) 空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(lists):
  # 插入排序
  count = len(lists)
  for i in range(1, count):
    key = lists[i]
    j = i - 1
    while j >= 0:
      if lists[j] > key:
        lists[j + 1] = lists[j]
        lists[j] = key
      j -= 1
  return lists

4希尔排序

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

时间复杂度：O(nlogn) 空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def shell_sort(lists):
  # 希尔排序
  count = len(lists)
  step = 2
  group = count / step
  while group > 0:
    for i in range(0, group):
      j = i + group
      while j < count:
        k = j - group
        key = lists[j]
        while k >= 0:
          if lists[k] > key:
            lists[k + group] = lists[k]
            lists[k] = key
          k -= group
        j += group
    group /= step
  return lists

5归并排需

归并过程为：比较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的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

时间复杂度：O(nlogn) 空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  return result
 
def merge_sort(lists):
  # 归并排序
  if len(lists) <= 1:
    return lists
  num = len(lists) / 2
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

6快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度：O(nlogn) 空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(lists, left, right):
  # 快速排序
  if left >= right:
    return lists
  key = lists[left]#最左边的值
  low = left #最低的id
  high = right #最高的id
  while left < right:
    while left < right and lists[right] >= key:
      right -= 1#从右边找到大于左边的
    lists[left] = lists[right]
    while left < right and lists[left] <= key:
      left += 1#从左边找到小于右边的
    lists[right] = lists[left]
  lists[right] = key
  quick_sort(lists, low, left - 1)
  quick_sort(lists, left + 1, high)
  return lists

7堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

时间复杂度：O(nlogn) 空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def adjust_heap(lists, i, size): #调整堆
  lchild = 2 * i + 1  #左子节点
  rchild = 2 * i + 2  #右子节点
  max = i  #父节点
  if i < size / 2: #父节点非叶子节点
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild #左叶子节点比父节点大
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild #右叶子节点比父节点大
    if max != i: #父节点不是最大
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size) #父节点变化重新调整
 
def build_heap(lists, size): #创建堆
  for i in range(0, (size/2))[::-1]: #从非叶子节点底部开始调整
    adjust_heap(lists, i, size) 
 
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size) #堆排序
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0] #顶部为最大值放到最后
    adjust_heap(lists, 0, i) #重新调整剩余元素

8计数排序

假设n个输入元素中每一个都是介于0到k之间的整数，此处k为某个整数。当k=O(n)时，计数排序的运行时间为Θ(n)。对每一个数的元素x，确定出小于x的元素个数。有了这一信息就可以把x直接放到最终输出数组中的位置上。

时间复杂度：O(n+k) 空间复杂度：O(k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countingSort(alist,k):
  n=len(alist)
  b=[0 for i in xrange(n)] #结果数组
  c=[0 for i in xrange(k+1)] #范围数组
  for i in alist:
    c[i]+=1
  for i in xrange(1,len(c)):
    c[i]=c[i-1]+c[i] #累加
  for i in alist:
    b[c[i]-1]=i #c[i]为alist中i的个数
    c[i]-=1
  return b
if __name__=='__main__':
  a=[random.randint(0,100) for i in xrange(100)]
  print countingSort(a,100)

9桶排序

如果有一个数组A，包含N个整数，值从1到M，我们可以得到一种非常快速的排序，桶排序（bucket sort）。留置一个数组S，里面含有M个桶，初始化为0。然后遍历数组A，读入Ai时，S[Ai]增一。所有输入被读进后，扫描数组S得出排好序的表。该算法时间花费O(M+N)，空间上不能原地排序。

时间复杂度：O(n+k) 空间复杂度：O(n+k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class node:  #桶节点
  def __init__(self,k):  
    self.key=k;  
    self.next=None;  #指针
  
def bucketsort(lista):  
  #初始化10个桶
  h=[];  
  for i in range(0,10):  
    h.append(node(0)); 
  #遍历节点 
  for i in range(0,len(lista)):  
    tmp=node(lista[i]);  
    map=lista[i]/10;  
    p=h[map];#找到对应的桶  
    if p.key is 0:  #空
      h[map].next=tmp;  
      h[map].key=h[map].key+1; #桶中数量加一 
    else:  #已存在节点
      while(p.next !=None and p.next.key<=tmp.key):#桶中的值小于插入值  
        p=p.next;  
      tmp.next=p.next;  
      p.next=tmp;  #插入节点
      h[map].key=h[map].key+1;  
  k=0;  
  #遍历桶
  for i in range(0,10):  
    q=h[i].next;  
    while(q != None ):  
      lista[k]=q.key;  
      k=k+1;  
      q=q.next;  
  return lista;  
lista=[1,4,23,45,97,22,10,4];   #桶排序测试代码  
bucketsort(lista);  
print lista;

10基数排序

基数排序一般用于长度相同的元素组成的数组。首先按照最低有效数字进行排序，然后由低位向高位进行。基数排序可以看做是进行多趟桶排序。每个有效数字都在0-9之间，很适合桶排序，建10个桶很方便。

时间复杂度：O(n*k) 空间复杂度：O(n+k)

1
2
3
4
5
6
7
8
9
10
11
12
import math
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      bucket[j/(radix**(i-1)) % (radix**i)].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
  return lists

深度优先遍历（scrapy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def depth_tree(node):
  if node is not None:
    print node.data
    if node.left is not None:
      return deep_tree(node.left)
    if node.right is not None:
      return deep_tree(node.right)
```   
# 广度优先遍历
```python
def level_queue(root):
  if root is NOne:
    return
  queue=[]
  node=root
  queue.append(node)
  while queue:
    node=queue.pop(0)
    print node.elem
    if node.lchild is not None:
      queue.append(node.lchild)
    if node.rchild is not None:
      queue.append(node.echild)