排序和查找

2018-02-18

排序

冒泡排序

时间复杂度：$O(n^2)$
paste image
从开始两个比较，将大值向后移动，直到吧最大值移到了最后的位置。再将第二大数移动到倒数第二个位置，直到完成。

array = [1,2,3,6,5,4]
def bubble_sort(list):
    array=list.copy()
    for i in range(len(array)):
        for j in range(len(array)-i-1):
            if array[j]>array[j+1]:
                array[j+1],array[j]=array[j],array[j+1]
    return array
print(bubble_sort(array))

选择排序

时间复杂度：$O(n^2)$
paste image
将最小值移动到第一个位置，然后第二小值移动到第二个位置，直到最后。

def select_sort(list):
    array=list.copy()
    for i in range(len(array)):
        for j in range(i,len(array)):
            if array[i]>array[j]:
                array[i],array[j]=array[j],array[i]
    return array
print(select_sort(array))

插入排序

时间复杂度：$O(n^2)$
paste image
将第一个与第二个比较，将小的放在前面，然后将第三放在对应有序的位置，直至最后都变有序。

def inser_sort(list):
    array=list.copy()
    print(array)
    for i in range(len(array)):
        for j in range(i,0,-1):
            if array[i]<array[j]:
                array[i],array[j]=array[j],array[i]
    return array
print(inser_sort(array))

归并排序

时间复杂度：$O(n·\log_ n)$
paste image
首先归并排序使用了二分法，归根到底的思想还是分而治之。拿到一个长数组，将其不停的分为左边和右边两份，然后以此递归分下去。然后再将她们按照两个有序数组的样子合并起来。

这里显示了归并排序的第一步，将数组按照middle进行递归拆分，最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。

两个有序数组排序的方法则非常简单，同时对两个数组的第一个位置进行比大小，将小的放入一个空数组，然后被放入空数组的那个位置的指针往后移一个，然后继续和另外一个数组的上一个位置进行比较，以此类推。到最后任何一个数组先出栈完，就将另外i一个数组里的所有元素追加到新数组后面。

由于递归拆分的时间复杂度是logN 然而，进行两个有序数组排序的方法复杂度是N该算法的时间复杂度是N*logN 所以是NlogN。

def merge(a,b):
    i=j=0
    c=[]
    while i<len(a) and j<len(b):
        if a[i]<=b[j]:
            c.append(a[i])
            i+=1
            if i==len(a):
                c+=b[j:]
        else:
            c.append(b[j])
            j+=1
            if j==len(b):
                c+=a[i:]
    return c
        
def merge_sort(list):
    if len(list)<=1:
        return list
    mid=int(len(list)/2)
    left=merge_sort(list[:mid])
    right=merge_sort(list[mid:])
    return merge(left,right)

array=[4, 7, 8, 3, 5, 9]
print(merge_sort(array))

快速排序

时间复杂度：$O(n·\log_ n)$
paste image

选取一个数字作为基准，可选取末位数字
将数列第一位开始，依次与此数字比较，如果小于此数，将小数交换到左边，最后达到小于基准数的在左边，大于基准数的在右边，分为两个数组

分别对两个数组重复上述步骤
paste image

def quick_sort(list):
    if len(list)<=1:
        return list
    left=[]
    right=[]
    for i in list[1:]:
        if i<=list[0]:
            left.append(i)
        else:
            right.append(i)
    return quick_sort(left)+[list[0]]+quick_sort(right)
quick_sort(array)

可以用一行实现快速排序：quick_sort = lambda array: array if len(array)<=1 else quick_sort([item for item in array[1:] if item<=array[0]]) + [array[0]] +quick_sort([item for item in array[1:] if item>array[0]])

用栈实现非递归的快排程序
需要考虑两个问题:
1）栈里边保存什么？
2）迭代结束的条件是什么？
栈里边保存的当然是需要迭代的函数参数，结束条件也是跟需要迭代的参数有关。对于快速排序来说，迭代的参数是数组的上边界low和下边界high，迭代结束的条件是low == high。

由于通过切片传递列表会对列表进行复制，所以需要传递索引，传入原列表，这样在执行操作时就可以改变原始列表了。

def quick_sort_stack(list,l=None,r=None):
    if l==None:
        l=0
    if r==None:
        r=len(list)-1
    if l>=r:
        return
    stack=[(l,r)]
    while stack:
        left,right = stack.pop(0)
        if right-left<=0:
            continue
        x=list[left]
        left_index=left+1
        for i in range(left+1,right+1):
            if list[i]<x:
                list[left_index],list[i]=list[i],list[left_index]
                left_index+=1
        list[left_index-1],list[left]=list[left],list[left_index-1]
        if left<left_index-1:
            stack.insert(0,(left,left_index-2))
        if left_index+1<right:
            stack.insert(0,(left_index,right))
        print(stack)
        print('list',list,list[left:left_index],list[left_index+1:right+1])
array=[4, 7, 8, 3, 5, 9]
quick_sort_stack(array)
print(array)

堆排序

时间复杂度：$O(n·\log_ n)$
paste image

这篇文章讲解的比较清楚
建立大小为n的大根堆，堆顶元素是这个元素的最大值。将堆顶值与最后一个元素交换，然后将最大值脱离堆结构，放在数组的最后的位置。再将n-1的元素构成大根堆。直到元素全部有序。

在这里首先要先解释一下什么是堆，堆栈是计算机的两种最基本的数据结构。堆的特点就是FIFO(first in first out)先进先出，这里的话我觉得可以理解成树的结构。堆在接收数据的时候先接收的数据会被先弹出。
栈的特性正好与堆相反，是属于FILO(first in/last out)先进后出的类型。栈处于一级缓存而堆处于二级缓存中。这个不是本文重点所以不做过多展开。
堆排序
堆可以分为大根堆和小根堆，这里用最大堆的情况来定义操作:

最大堆调整(MAX_Heapify):将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值。当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，当i根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。
建立最大堆(Build_Max_Heap):将堆所有数据重新排序。建堆的过程其实就是不断做最大堆调整的过程，从len/2出开始调整，一直比到第一个节点。

堆排序(HeapSort):移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。首先先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len-1个节点继续做堆调整的过程。直到将所有的节点取出，对于n个数我们只需要做n-1次操作。
参考代码

def heap_adjust(list,start,end):
   root=start
    while True:
       child=2*root+1
        if child>end:
           break
        if child+1<end and list[child]<list[child+1]:
           child+=1
        if list[root]<list[child]:
           list[root],list[child]=list[child],list[root]
            root=child
        else:
           break      
def heap_sort(list):
   # 创建最大堆
    for start in range((len(list) - 2) // 2, -1, -1):
       heap_adjust(list,start, len(list) - 1)
    # 堆排序
    for end in range(len(list) - 1, 0, -1):
       list[0], list[end] = list[end], list[0]
        heap_adjust(list,0, end - 1)
array=[4, 7, 8, 3, 5, 9]
heap_sort(array)
print(array)

希尔排序

时间复杂度：$O(n·\log_ n)$
希尔排序是插入排序的一个调整，步长是可变的。
paste image
首先看步长为3，查找如果小于前面的第3个数，则交换，然后再查找前面的第3个数，如果不小于则停止。

整个数组排序完成后，再用步长为2的排序，再用步长为1的排序。
参考代码

def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = gap // 2
    return list

锦标赛排序

时间复杂度：$O(n·\log_ n)$
paste image

桶排序

桶排序是一种思想，比较常规的是计数排序和基数排序。桶排序的速度非常之快，比其他排序算法快非常多，但是需要占用大量空间。
代码参考

def bucket(list):
    bucket_list=[0]*(max(list)-min(list)+1)
    for i in list:
        bucket_list[i]+=1
    ret=[]
    for i,val in enumerate(bucket_list):
        if val:
            ret+=[i for j in range(val)]
    return ret
a =[12,4,2,4,56,1,4,0]
b = bucket(a)
print(b)