算法 - 简单查找排序的 Python 实现

算法

查找排序

hanoi

# 汉诺塔问题

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n - 1, a, c, b)
        print('Move from %s to %s' % (a, c))
        hanoi(n - 1, b, a, c)


hanoi(3, 'A', 'B', 'C')

顺序查找

"""
顺序查找
"""
"""
时间复杂度：O(n)
python内置的  列表查询函数 index() 就是顺序查找  ------------->  因为二分查找的前提是有序列表

而排序的时间复杂段往往要大于查找，所以就要考虑了
如果是要进行大量的查找，那么先排序可能会更好
"""


def linear_search(li, val):
    for i, v in enumerate(li):
        if v == val:
            return i
    else:
        return None


ret = linear_search([1, 2, 3, 4], 10)
print(ret)

二分查找

"""
二分查找
时间复杂度：O(logN)
"""
"""
时间复杂度：O(logN)
当计算时间复杂度时，一旦有  循环减半  一般会有 logN
"""


def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left < right:
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None


ret = binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)
print(ret)

冒泡排序

"""
冒泡排序
"""
import random

"""
时间复杂度：  O(n*n)
"""


def bubble_sort(li):
    for i in range(len(li) - 1):  # 一共循环几次
        exchange = False
        for j in range(len(li) - i - 1):  # 每次循环比较几次
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                exchange = True
        if not exchange:  # 判断是否已经排序完成
            return


li = [random.randint(0, 10000) for i in range(10)]
print(li)
bubble_sort(li)
print(li)

选择排序

"""
选择排序
"""
import random


def select_sort_simple(li):
    """
    时间复杂度：  O(n*n)
    """
    new_li = []
    for i in range(len(li)):
        min_num = min(li)  # min函数本身就是一个 O(n) 的操作
        new_li.append(min_num)
        li.remove(min_num)  # remove操作本身就是一个 O(n) 的操作
    return new_li


def select_sort(li):
    """
    时间复杂度：  O(n*n)
    """
    for i in range(len(li) - 1):  # i是第几趟
        min_loc = i
        for j in range(i, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


li = [random.randint(0, 10000) for i in range(10)]
print(li)
print(li)

插入排序

"""
插入排序
"""

import random

"""
每次在 未排序区 中拿一个，在 已排序区 中插入
第一次默认已经拿了一个


时间复杂度 ： O(n*n)
"""


def insert_sort(li):
    for i in range(1, len(li)):  # i:本次摸到牌的下标
        tem = li[i]
        j = i - 1  # 已经在排序区的最大的值的下标
        while j >= 0 and li[j] > tem:
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tem
        print(li)


li = [random.randint(0, 100) for i in range(6)]
print(li)
insert_sort(li)
print(li)

快速排序

"""
快速排序
"""

"""
1. 先定义一个基准元素
2. 使其元素左边的子序列都小于该元素，其元素右边的子序列都大于该元素
3. 在对两边的子序列递归排序

时间复杂度 ：               O(N*logN)
最坏的情况下时间复杂度为 ：    O(N*N)
"""



def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:  # 在右边找比tmp小的值，找到赋值给left空位
            right -= 1
        li[left] = li[right]
        print(li2, '赋值给left空位')
        while left < right and li[left] <= tmp:  # 在左边找比tmp大的值，找到赋值给right空位
            left += 1
        li[right] = li[left]
        print(li2, '赋值给right空位')
    li[left] = tmp  # 当left和right相同时，将基准元素放到空位，就实现了左边小右边大
    print(li2)
    return left


def quick_sort(li, left, right):
    if left < right:  # 表示至少两个元素
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)


# li = [5, 7, 3, 1, 4, 6, 2, 9, 8]
li2 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(li2)
quick_sort(li2, 0, len(li2) - 1)
print(li2)

"""
最坏情况；    O(N*N)

[9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 8, 7, 6, 5, 4, 3, 2, 1] 赋值给left空位
[1, 8, 7, 6, 5, 4, 3, 2, 1] 赋值给right空位
[1, 8, 7, 6, 5, 4, 3, 2, 9]
[1, 8, 7, 6, 5, 4, 3, 2, 9] 赋值给left空位
[1, 8, 7, 6, 5, 4, 3, 2, 9] 赋值给right空位
[1, 8, 7, 6, 5, 4, 3, 2, 9]
[1, 2, 7, 6, 5, 4, 3, 2, 9] 赋值给left空位
[1, 2, 7, 6, 5, 4, 3, 2, 9] 赋值给right空位
[1, 2, 7, 6, 5, 4, 3, 8, 9]
[1, 2, 7, 6, 5, 4, 3, 8, 9] 赋值给left空位
[1, 2, 7, 6, 5, 4, 3, 8, 9] 赋值给right空位
[1, 2, 7, 6, 5, 4, 3, 8, 9]
[1, 2, 3, 6, 5, 4, 3, 8, 9] 赋值给left空位
[1, 2, 3, 6, 5, 4, 3, 8, 9] 赋值给right空位
[1, 2, 3, 6, 5, 4, 7, 8, 9]
[1, 2, 3, 6, 5, 4, 7, 8, 9] 赋值给left空位
[1, 2, 3, 6, 5, 4, 7, 8, 9] 赋值给right空位
[1, 2, 3, 6, 5, 4, 7, 8, 9]
[1, 2, 3, 4, 5, 4, 7, 8, 9] 赋值给left空位
[1, 2, 3, 4, 5, 4, 7, 8, 9] 赋值给right空位
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9] 赋值给left空位
[1, 2, 3, 4, 5, 6, 7, 8, 9] 赋值给right空位
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

计算运行时间的装饰器

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2 - t1))
        return result

    return wrapper