选择排序

选择排序是一种简单、低效的排序方法。
他每次都从序列中按顺序搜索寻找最值,所以总的查找次数为n,n-1, n-2, n-3, ……, 1
大O表示法:O(n^2)
注意:大O表示法忽略常数1/2.

def findSmallest( arr ):
    smallest_index = 0
    for i in range(1, len(arr)):
        if( arr[i] < arr[smallest_index] ):
            smallest_index = i
    return smallest_index

def selectSort( arr ):
    newArr = []
    rag = range( len(arr) )
    for i in rag:
        smallest_index = findSmallest( arr )
        newArr.append( arr.pop( smallest_index ) )
    return newArr

print( selectSort([5,4,7,10,3,20]) )

[3, 4, 5, 7, 10, 20]
更多的排序算法,可以查看文章:https://blog.csdn.net/theArcticOcean/article/details/50993858

递归

递归:自己调用自己的现象,通常有迭代条件和终止条件。
和循环相比,递归更加容易让人理解算法的思路,但是需要存储额外的函数调用的栈信息。
下面是计算斐波那契数列的例子:

def Fib( x ):
    if( x < 2 ):
        return x
    else:
        return Fib(x-1) + Fib(x-2)

print( Fib(7) ) #13

二分查找

针对有序列表的查找问题,二分查找是一种优秀的算法,他在每次查找错误后都会调整出新的查找区间,不断缩小范围。
例如,如果列表是从小到大,找的目标比真实目标大,那么就继续查找左区间,比它大就查找右区间,找到了直接退出,一直这样迭代就行下去。
时间复杂度为 O (logn)

# for key:find '==' value
def binary_search(key):
    length=len( array )
    ans=length-1
    l=0
    r=length-1
    while(l<=r):
        mid=(l+r)>>1
        if(array[mid]<key):
            l=mid+1
        elif(array[mid]>key):
            r=mid-1
        else:
            return mid

array=[ 4, 2, 6, 1, 45, 23, 27, 12, 89, 5 ]
array.sort()
print( array )
print( "position is ", binary_search( 27 ) )

更多二分问题,可以阅读:https://blog.csdn.net/theArcticOcean/article/details/50408776

分类: Algorithm

发表评论

电子邮件地址不会被公开。 必填项已用*标注