排序算法

2019-04-03  本文已影响0人  AmaAnchor

折半查找

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/2k..直到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要小得多,因此快速排序大多数情况下更快。

上一篇 下一篇

猜你喜欢

热点阅读