算法学习

---

二分查找

#-*-coding:utf-8-*-

def binary_search(list,item):
    low = 0
    high = len(list)-1

    while low<=high:
        mid = (low+high)/2
        guess = list[mid]
        if guess==item:
            return mid
        if guess<item:
            low = mid + 1
        else:
            high = mid -1
    return None

def main():
    my_list = [1,2,4,5,8,9,11,13,16,18,20,21,22,23,25,26,28,30]
    res = binary_search(my_list,8)
    if res == None:
        print "未找到!"
    else:
        print "已找到，位置在第"+str(res)+"个."

if __name__ == '__main__':
    main()

选择排序

#-*-coding:utf-8-*-

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

def selectionSort(arr):
    newarr = []
    for i in range(len(arr)):
        smallest = findsmallest(arr)
        newarr.append(arr.pop(smallest))
    return newarr

def main():
    print selectionSort([9,4,6,71,5,8,27,36,25,55,12,59,21,45,49,27])

if __name__ == '__main__':
    main()

快速排序

#-*-coding:utf-8-*-

def QuickSort(arr):
    if len(arr) <= 1:
        return arr
    else:
        tmp = arr[0]
        less = [i for i in arr[1:] if i <= tmp]
        greater = [i for i in arr[1:] if i > tmp]
        return QuickSort(less)+[tmp]+QuickSort(greater)

def main():
    print QuickSort([8,10,94,25,55,45,78,30,12,25,99,61])

if __name__ == '__main__':
    main()