1, search,

1) Sequential search complexity O(n) Sequential search of unordered lists:

# -*- codind: utf-8 -*-

def sequentialSearch(alist, item):
    pos = 0
    found = False
    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1
    return found

if __name__ == '__main__':
    testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
    print(sequentialSearch(testlist, 3))
    print(sequentialSearch(testlist, 13))
Copy the code

Sequential search of sequential lists:

def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos = pos + 1
    return found

if __name__ == '__main__':  
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
    print(orderedSequentialSearch(testlist, 3))
    print(orderedSequentialSearch(testlist, 13))
Copy the code

Binary search:

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


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = ( first + last)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint -1
            else:
                first = midpoint +1
    return found

if __name__ == '__main__':
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
    print(binarySearch(testlist, 3))
    print(binarySearch(testlist, 13))
Copy the code

Binary search recursive version

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


def binarySearch(alist, item):
    if len(alist) == 0 :
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch (alist[:midpoint],item)
            else:
                return binarySearch (alist[midpoint+1:],item)

if __name__ == '__main__':
    testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
    print(binarySearch(testlist, 3))
    print(binarySearch(testlist, 13))
Copy the code

2, sorting,

Bubble sort complexity: O(n^2)

Def bubbleSort(alist): for passnum in range(len(alist)-1,0,-1): def bubbleSort(alist): for passnum in range(passnum): if [I]>alist[I +1]: temp = alist[i] alist[i] = alist[i+1] alist[i+1] = temp if __name__ == '__main__': Alist = [54,26,93,17,77,31,44,55,20] the bubbleSort (alist) print (alist)Copy the code

Selection sort O(n^2)

Def selectionSort(): for fillslot in range(len(alist)-1,0,-1): positionOfMax=0 for location in range(1,fillslot+1): if alist[location]>alist[positionOfMax]: positionOfMax = location temp = alist[fillslot] alist[fillslot] = alist[positionOfMax] alist[positionOfMax] = temp if __name__ = = "__main__ ': alist = [54,26,93,17,77,31,44,55,20] selectionSort (alist) print (alist)Copy the code

Insert sort: O(n^2)

def insertionSort(alist): for index in range(1,len(alist)): currentvalue = alist[index] position = index while position>0 and alist[position-1]>currentvalue: alist[position]=alist[position-1] position = position-1 alist[position]=currentvalue if __name__ == '__main__': Alist = [54,26,93,17,77,31,44,55,20] insertionSort (alist) print (alist)Copy the code