1. 查找

1.1 顺序查找

思路：从第一个元素开始，逐个往后比对，找到为止

代码实现如下：

# 顺序查找
def sequential_search(alist,item):
    pos = 0
    found = False
    while pos < len(alist) and (not found):
        if alist[pos] == item:
            found = True
        else:
            pos += 1
    return found

1.2 二分查找

条件：数组必须有序

思路：每次找中间元素，一半直接排除，缩小范围

（1）递归版代码

def binary_search(alist,item):
    order = 0 # 默认0为从大到小的有序列表，1为从小到大的有序列表
    position = len(alist)//2  # 取中间位置
    found = False
    new_list = []
    global count
    if len(alist) > 1 and alist[0] < alist[1]:
        order = 1
    if alist[position] == item:
        found = True
    elif alist[position] != item and order == 0:
        count +=1
        if item < alist[position]:
            new_list = alist[position:]
            return binary_search(new_list,item)
        elif item > alist[position]:
            new_list = alist[:position]
            return binary_search(new_list,item)
    elif alist[position] != item and order == 1:
        count +=1
        if item < alist[position]:
            new_list = alist[:position]
            return binary_search(new_list,item)
        elif item > alist[position]:
            new_list = alist[position:]
            return binary_search(new_list,item)
    return found,count

递归版代码引用了全局变量count每次重新调用函数时需重新定义count的值，且其无法返回原始索引。

（2）迭代版代码

def binary_search(alist,item):
    first = 0
    last = len(alist)-1
    found = False
    count = 1
    order = 0 # 默认0为从大到小的有序列表，1为从小到大的有序列表
    if len(alist) > 1 and alist[0] < alist[1]:
        order = 1
    while first <= last and (not found) and order == 1:
        mid_point = (first+last)//2  # 定义中间位置
        if alist[mid_point] == item:
            found = True
        else:
            count +=1
            if item < alist[mid_point]:
                last = mid_point-1
            else:
                first = mid_point+1
    while first <= last and (not found) and order == 0:
        mid_point = (first+last)//2  # 定义中间位置
        if alist[mid_point] == item:
            found = True
        else:
            count +=1
            if item < alist[mid_point]:
                first = mid_point+1
            else:
                last = mid_point-1
    return found,count

递归版和迭代版的代码操作数最多相差一，二者的复杂度相同，但迭代版没有递归版上面的缺点。

2. 排序

2.1 冒泡排序

思路：相邻元素两两比较，大的往后冒，像水泡上浮

# 冒泡排序
def bubble_sort(alist):
    for j in range(len(alist)-1):
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                a = alist[i]  # a为较大数
                alist[i] = alist[i+1]
                alist[i+1] = a
    return alist
li = [5,3,4,9,6,7,344,42,67]
print(bubble_sort(li)) 

2.2 选择排序

思路：每一轮选最小 / 最大放到已排序末尾

def selection_sort(alist):
    # 选择排序
    for i in range(len(alist)-1):
        a = 0  # 下标
        for j in range(1,len(alist)-i):
            if alist[j] > alist[a]:
                a = j
        temp = alist[a]  # 最大值
        alist[a] = alist[len(alist)-i-1]
        alist[len(alist)-i-1] = temp
    return alist
li = [5,3,4,9,6,7,3,4,5,6,7,8,9,10,1,1,2,3,4,5,6,6,7,7,77]
print(selection_sort(li))

2.3 插入排序

思路：把后面元素插入到前面有序序列合适位置

步骤：

（1）获取所有数据项及其位置

（2）从0位置开始抽取（按照位置顺序抽取数据项）

（3）第一个抽取的数据项放在0号槽

（4）后续抽取的数据项与前一个数据项对比大小，如果其小于前一个数据项，则二者交换位置，新抽取的数据项在新位置继续判断直到找到合适的位置

def insertion_sort(alist):
    # 插入排序
    for i in range(1,len(alist)):
        # 获取第一个数据项以外的其他数据项及其位置
        position = i
        current_value = alist[position]
        while position > 0 and current_value < alist[position-1]:
            # 如果即将插入的数据项小于前一个数据项，则二者互换位置，前者继续判断
            alist[position] = alist[position-1]
            position = position - 1
        alist[position] = current_value  # 判断结束后将数据项插入新位置
    return alist

2.4 谢尔排序

思路：分组插入排序，先粗调、后细调

列表越接近有序，插入排序的比对次数就越少，从这种情况出发，谢尔排序以插入排序作为基础，对无序表进行‘间隔’划分子列表，每个子列表都执行插入排序。

def shell_sort(alist):
    sublist_count = len(alist)//2
    while sublist_count > 0:
        for start_position in range(sublist_count):
            gap_insertion_sort(alist,start_position,sublist_count)
        sublist_count = sublist_count//2
    return alist
def gap_insertion_sort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        current_value = alist[i]
        position = i
        while position >= gap and alist[position-gap] > current_value:
            alist[position] = alist[position-gap]
            position = position-gap
        alist[position] = current_value

2.5 归并排序

思路：先拆成两半，再合并有序序列，反复执行并返回调整后的有序序列。

def merge_sort(lst):
    # 归并排序
    if len(lst) <= 1:
        return lst
    middle = len(lst)//2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged

2.6 快速排序

思路：选基准值，小放左、大放右，分治递归

def quick_sort(alist):
    # 快速排序
    quick_sort_help(alist,0,len(alist)-1)
def quick_sort_help(alist,first,last):
    if first < last:
        split_point = partition(alist,first,last)
        quick_sort_help(alist,first,split_point-1)
        quick_sort_help(alist,split_point+1,last)
def partition(alist,first,last):
    pivot_value = alist[first]
    left_mark = first
    right_mark = last
    done = False
    while not done:
        while left_mark <= right_mark and alist[left_mark] <= pivot_value:
            left_mark = left_mark +1
        while alist[right_mark] >= pivot_value and right_mark >= left_mark:
            right_mark = right_mark -1
        if right_mark < left_mark:
            done = True
        else:
            temp = alist[left_mark]
            alist[left_mark] = alist[right_mark]
            alist[right_mark] = temp
    temp = alist[first]
    alist[first] = alist[right_mark]
    alist[right_mark] = temp
    return right_mark