programnote

一、排序
1.冒泡排序(bubble sort)
每循环一次都会在已经确定顺序的部分加一个元素
复杂度O(n^2)
a=[3,2,4,1,5,6]
n=len(a)
for i in range(n-1,0,-1):
  for j in range(0,i):
    if a[j]>a[j+1]:
      tmp=a[j]
      a[j]=a[j+1]
      a[j+1]=tmp
print(a)

存在某次交换之后就排好序的情况，可以加入flag，如果一次循环后没有发生交换，则flag不变，说明已经排好序
2.快速排序(quick sort)
分治思想  从数列中取出一个key值，比他小的放左边，比他大的放右边，对左右两边继续进行这个步骤。
复杂度O(nlogn)
递归：
a=[72,6,57,88,60,42,83,73,48,85]
def quicksort(a,left,right):
    if left>right:
        return 
    low=left;high=right
    key=a[left]

    while left<right:
        while left<right and a[right]>key:
            right-=1
        a[left]=a[right]
        while left<right and a[left]<key:
            left+=1
        a[right]=a[left]
    a[left]=key
    quicksort(a,low,left-1)
    quicksort(a,left+1,high)

3.归并排序(merge sort)
进行二分，然后每次合并两个有序数组
def merge(a,b):
    m=len(a);n=len(b)
    i=0;j=0
    c=[]
    while i<m and j<n:

        if a[i]>b[j] :
            c.append(b[j])
            j+=1
        else:
            c.append(a[i])
            i+=1
    if i==m:
        for item in b[j:]:
            c.append(item)
    else:
        for item in a[i:]:
            c.append(item)

    return c
def mergesort(a):
    if len(a)<=1:
        return a
    m=int(len(a)/2)
    left=mergesort(a[:m])
    right=mergesort(a[m:])
    print('left',left)
    print('right',right)
    ans=merge(left,right)
    print('ans',ans)
    return ans
a=[3,4,34,2,68,18,5,5,20,21]
c=mergesort(a)
4.堆排序(heapsort)
构建大根堆（一个完全二叉树，它的根节点总是大于等于左右子树节点），然后每次取出根节点的数据
完全二叉树：除了最下面一层都被填满元素，并且最下面一层是左对齐的