1、冒泡排序 - 实现列表[5, 3, 4, 7, 2]排序:

# 冒泡法实现列表排序
def bubble_sort(alist):
    """冒泡排序"""
    # 数列的长度
    n = len(alist)

    # 控制比较轮数
    for j in range(0, n - 1):
        # 计数
        count = 0
        # 控制每一轮的比较次数
        for i in range(0, n - j - 1):
            # 比较相邻的；两个数字，不符合要求交换位置
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                count += 1
        # 如果遍历一遍发现没有数字交换，退出循环，证明数列有序
        if count == 0:
            break


if __name__ == '__main__':
    alist = [5, 3, 4, 7, 2]
    bubble_sort(alist)
    print(alist)

• 冒泡排序运行结果：

冒泡排序运行结果.png

2、选择排序 - 实现列表[1, 3, 4, 10, 0, 1000, 88]排序：

def select_sort(alist):
    """选择排序"""

    # 列表的长度
    n = len(alist)

    # 控制比价轮数
    for j in range(0, n - 1):
        # 假定的最小值的下标
        min_index = j

        # 控制比较次数
        for i in range(j + 1, n):
            # 进行比较获得最小值
            if alist[i] < alist[min_index]:
                min_index = i

        # 如果假定的最小值下标发生了变化，那么就进行交换
        if min_index != j:
            alist[j], alist[min_index] = alist[min_index], alist[j]


if __name__ == '__main__':
    alist = [1, 3, 4, 10, 0, 1000, 88]
    select_sort(alist)
    print(alist)

• 选择排序运行结果：

选择排序运行结果.png

3、插入排序 - 实现列表[1, 100, 99, 20, 5, 1000]排序：

def insert_sort(alist):
    """插入排序"""
    # 列表的长度
    n = len(alist)

    # 控制轮数
    for j in range(1, n):
        # [j, j-1, j-2, ……，,1]
        # 找到合适的位置安放我们的无序的数据
        for i in range(j, 0, -1):
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
            else:
                break


if __name__ == '__main__':
    alist = [1, 100, 99, 20, 5, 1000]
    print("原来的列表：", alist)
    insert_sort(alist)
    print("排序后的列表：", alist)

• 插入排序运行结果：

插入排序运行结果.png

4、快速排序 - 实现列表[1, 3, 100, 50, 1000, 0, 1, 1]排序：

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的结束条件
    if start >= end:
        return

    # 界限值
    mid = alist[start]
    # 左右游标
    left = start
    right = end

    while left < right:
        # 从右边开始找寻小于mid的值 归类到左边
        while alist[right] >= mid and left < right:
            right -= 1
        alist[left] = alist[right]
        # 从左边开始找寻大于mid的值 归类到左边
        while alist[left] < mid and left < right:
            left += 1
        alist[right] = alist[left]

    # 循环一旦结束了 证明找到了mid应该在的位置
    alist[left] = mid

    # 递归操作
    quick_sort(alist, start, left - 1)
    quick_sort(alist, right + 1, end)


if __name__ == '__main__':
    aist = [1, 3, 100, 50, 1000, 0, 1, 1]
    quick_sort(aist, 0, len(aist) - 1)
    print(aist)

• 快速排序运行结果：

快速排序运行结果.png

5、二分查找（1）递归法 - 查找元素是否在列表[1, 3, 6, 31, 100]中：

def binary_search(alist, item):
    """二分查找"""

    # 获取数列的长度
    n = len(alist)
    # 递归的结束条件
    if n == 0:
        return False

    # 中间值
    mid = n // 2

    if item == alist[mid]:
        return True
    elif item < alist[mid]:
        return binary_search(alist[0:mid], item)
    elif item > alist[mid]:
        return binary_search(alist[mid + 1:], item)
    else:
        return False


if __name__ == '__main__':
    alist = [1, 3, 6, 31, 100]
    print('31是否在列表[1, 3, 6, 31, 100]：', binary_search(alist, 31))
    print('32是否在列表[1, 3, 6, 31, 100]：', binary_search(alist, 32))

 

• 二分查找递归法运行结果：

二分查找递归法运行结果.png

6、二分查找（2）非递归法 - 查找元素是否在列表[1, 3, 6, 31, 100]中：

def binary_search(alist, item):
    """二分查找"""

    # 设置起始位置 获取中间值
    start = 0
    end = len(alist) - 1

    while start <= end:
        # 中间值
        mid = (start + end) // 2

        if item == alist[mid]:
            return True
        elif item < alist[mid]:
            end = mid - 1
        elif item > alist[mid]:
            start = mid + 1
    # 没有找到想要的数字
    return False


if __name__ == '__main__':
    alist = [1, 2, 3, 4, 5]
    print('1是否在列表[1, 2, 3, 4, 5]中：', binary_search(alist, 1))
    print('100是否在列表[1, 2, 3, 4, 5]中：', binary_search(alist, 100))

• 二分查找非递归法运行结果：

二分查找非递归法运行结果：.png