排序算法

折半查找

def bisearch(a,x,low,high):
    while low<=high:
        mid=(low+high)//2
        print('当前mid值：',mid)
        if a[mid]==x:
            return mid
        elif a[mid]<x:
            low=mid+1
        else:
            high=mid-1
    return 0

复杂度分析：
设查找次数为k
要查找的数组长度为：n,n/2,n/4,n/2^k..直到n/2k等于1，此时解出k=log2n
时间复杂度为O(n)=log2n
**大O表示法：‘长远主流’

选择排序

version1：出错的版本

def choose_sort(arr):
    for i in range(len(arr)):
        temp=arr[i]
        k=i
        for j in range(i+1,len(arr)):
            if temp>arr[j]:
                temp=arr[j]
                k=j
        if arr[i]<temp:#由于temp的有效范围，此时的temp为外层for下面的temp，并非在内层for中修改后的temp，所以这个算法在c中是对的，在python中要修改
            temp=arr[i]
            arr[i]=arr[k]
            arr[k]=temp

version2:改进部分：每一次比较都做一次交换，使得arr[smallest]保持为最小的值

def choose_sort2(arr):
    for i in range(len(arr)):
        smallest=i#保存最小值的坐标
        for j in range(i+1,len(arr)):
            if arr[smallest]>arr[j]:
                temp=arr[smallest]
                arr[smallest]=arr[j]
                arr[j]=temp

1	2	3	4	5	6

快速排序（分治思想）

分区函数

def partion(arr,low,high):
    i,j=low,high
    temp=arr[i]#取第一个数为基准值
    while i<j:#当i==j时，说明此时已经找到了基于基准值的分解点。
        while arr[j]>temp & i<j:
            j-=1
        if i>=j:#此处为第一次纠错点
            break
        arr[i]=arr[j]
        i+=1
        while (arr[i]<temp) & (i<j):#代码纠错：原因是&运算符的优先级过高。
            i+=1
        if i>=j:
            break
        arr[j]=arr[i]
        j-=1
    arr[i]=temp
    return i

def quicksort(arr,low,high):
    if low<high:
        x=partion(arr,low,high)
        quicksort(arr,low,x-1)
        quicksort(arr,x+1,high)

关于一个算法的运行时间，通常考量两点：
1，大O表示法的时间复杂度
2，基本操作的时间常量C

对于O(n)相同的两种算法，再考量时间常量C
比如归并算法和快速排序算法。平均时间复杂度都是O(nlog2n)，但快速排序的时间常量C要小得多，因此快速排序大多数情况下更快。