基本算法

1.二分查找

def bin_search(data,value):
    low=0
    high=len(data)-1
    while low<high:
        mid=(low+high)//2
        if data[mid]==value:
            return mid
        elif data[mid]<value:
            low=mid+1
        else:
            high=mid-1

2.冒泡排序

def bubble_sorted(data):
    for i in range(len(data)):
        #如果列表在一开始的时候就已经排好序,那么我们提供exchange标识位即可判断直接跳出
        exchange=False
        for j in range(len(data)-i-1):
            if data[j]>data[j+1]:
                data[j],data[j+1]=data[j+1],data[j]
                exchange=True
        if not exchange:
            return data

3.插入排序

def insert_sorted(data):
    for i in range(1,len(data)):
        tmp=data[i]
        j=i-1
        while j>=0 and tmp<data[j]:
            data[j+1]=data[j]
            j=j-1
        data[j+1]=tmp

4.快排

思路:取第一个元素P,使P先归位,列表被P分成两部分,左边的都比元素P小,右边的都比元素P大。之后递归完成排序

def quick_sorted(data,left,right):
    i=left
    j=right
    if i>j:
        return data
    tmp=data[left]
    while left<right:
        while left<right and data[right]>=tmp:
            right+=1
        data[left]=data[right]
        while left <right and data[left]<=tmp:
            left+=1
        data[right]=data[left]
    data[left]=tmp
    quick_sorted(data,left,i-1)
    quick_sorted(data,j+1,right)
    return data

5.堆排序

 思路:

  1.建立堆

  2.得到堆顶元素,为最大元素

  3.去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使堆有序。

  4.堆顶元素为第二大元素。

  5.重复步骤3,直到堆变空。

 代码自行百度~~~

6.希尔排序

希尔排序是一种分组插入排序算法。 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻量元素之间距离为d1,在各组内进行直接插入排序; 取第二个整数d2=d1/2,重复上述分组排序过程,直到di=1,即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不使某些元素有序,而是使整体数据越来越接近有序;最后一趟排序使得所有数据有序。

def shell_sorted(data):
    gap=len(data)//2
    while gap>0:
        for i in range(gap,len(data)):
            tmp=data[i]
            j=i-gap
            while j>=0 and tmp<data[j]:
                data[j+gap]=data[j]
                j-=gap
            data[j+gap]=tmp
        gap/=2