Python实现算法(一)

1.二分查找

def binary_search(mylist, item):
    low = 0
    high = len(mylist)-1
    while low <= high:
        mid = (low + high)//2     # 如果(low + high)//2不是偶数，Python自动将mid向下圆整。
        guess = mylist[mid]
        if guess == item:
            return mid
        if guess > item:          # 猜的数大了
            high = mid - 1
        else:                     # 猜的数小了
            low = mid + 1
    return None


my_list = [1, 3, 4, 5, 7, 9]
print(binary_search(my_list, 3))

大O 表示法指出了最糟情况下的运行时间.(除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在后面讨论)
这里顺带说一下简单查找法的算法运行时间为O(n),而二分查找法的运行时间为O(log n)

2.选择排序

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

print(selectionSort([5, 3, 6, 2, 10]))

选择排序算法运行时间为O(n²)

3.快速排序

def quicksort(array):
    if len(array) < 2:
        return array        # 基线条件：为空或只包含一个元素的数组是“有序”的
    else:
        pivot = array[0]    # 递归条件
        less = [i for i in array[1:] if i <= pivot]    # 由所有小于基准值的元素组成的子数组
        greater = [i for i in array[1:] if i > pivot]  # 由所有大于基准值的元素组成的子数组
        return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

快速排序算法运行时间为O(nlog n)
注:何为平均情况，何为最糟情况呢? 快速排序的性能高度依赖于你选择的基准条件,快速排序算法最糟糕的情况下运行时间为O(n²),最佳情况为O(nlog n),最佳情况也是平均情况.只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一，也是D&C (divide and conquer)典范.

关于大O表示法,算法时间复杂度,可查看这个链接https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation