查找和排序

2021-01-21

查找

顺序查找折半查找

# -*- coding: utf-8 -*-
"""
author: jueluo
annotation: 顺序查找和折半查找
"""
import time


# 计时装饰器
def timer(func):
    def wrapper(*args, **kwargs):  # 不知道查找函数到底有多少参数事使用*args *args是一个数组 **kwargs是字典
        start = time.time()
        end = time.time()
        print("time: %s" % (end - start))
        return func(*args, **kwargs)

    return wrapper


# 顺序（线性）查找 O(n)
@timer
def line_search(lst, val):
    for index, value in enumerate(lst):
        if val == value:
            return index
    return None


# 二分查找(需要有序) O(logn)
@timer
def binary_search(lst, val):
    low = 0
    high = len(lst) - 1

    while low <= high:
        mid = (high + low) // 2  # // floor 地板除
        if lst[mid] == val:
            return mid
        elif lst[mid] < val:
            low = mid + 1
        else:
            high = mid - 1

    return None


if __name__ == '__main__':
    lst = list(range(100))
    # print(lst)
    ret = line_search(lst, 2)
    print('-----',ret)

    # ret = binary_search(lst, 90000)
    # print(ret)

排序

插入排序

这些必须掌握的知识，不要觉得太简单，自己明了算法思想。还是稳妥写出来。拿到一个待排序列表，从第二个元素(数组下标为1)开始，将其作为待插入元素，首先和紧邻的前一个元素比较，如果小于它，则它需要进行下面的找到自己正确的位置(默认从小到大排序)，index=i,temp=lis[i],分别记录当前元素下标以及值。接下来不断和之前的元素相比较，i的遍历范围是range(j-1,-1,-1),即从待插入元素的上一个紧邻元素开始，一直找到正确的位置，循环体逻辑是lis[j] > temp 就说明待插入元素还更小，需要lis[j+1] = lis[j]更改元素，同时index更新为j，这个index为了待插入元素的最后位置，接着执行range(j-1,-1,-1)，这个循环直到j到0就跳出，最后lis[index] = temp。

简单选择排序

每次选择最小的元素，提到简单选择排序，这就是大家耳熟能详的回答，talk is really cheap，从i出发，range(0,n) ,比如第一轮，min为i，从0开始，j的范围是range(i+1,n),比较lis[min]>lis[j],min=j，min是在j的range(i+1,n)循环里不断改变的，（如果不能做到min=j写在循环里还是循环外，这就是没掌握）,跳出j的循环，就找到本轮的最小值，lismin]和lis[j]互换。接着i为1，又开始寻找剩下元素中最小的元素。

冒泡排序

有很多实现方式，关键你能马上写出来，不然真的太廉价了。大家都知道每趟选出最大(小)的元素，我的index为range(0,n)出发，首先考虑每轮确定一个元素在其最终位置，所以比较范围应该动态变换，设定i为range(0,n-index)，这个是针对自小到大的排序，每轮找出最大的元素，lis[i-1]>lis[i],两者交换位置。为了使已经有序的序列不用继续比较，设置一个flag，这个flag位置放在哪，如果你不熟悉，那也白给。

# -*- coding:utf-8 -*-
import time
"""
author: jueluo
"""

def timer(func):
    # 计时装饰器
    def wrapper(*args, **kwargs):  # 不知道查找函数到底有多少参数事使用*args *args是一个数组 **kwargs是字典
        start = time.time()
        end = time.time()
        print("time: %s" % (end - start))
        return func(*args, **kwargs)

    return wrapper


def insert_sort(lis):
    """
    :param lis: 待排序列表
    :return: 有序
    """
    n = len(lis)
    for i in range(1, n):
        if lis[i] < lis[i - 1]:
            index = i
            temp = lis[i]
            # 针对这个待插入元素 与之前的元素不断比较 直到找到一个比它小
            for j in range(i - 1, -1, -1):
                if lis[j] > temp:
                    lis[j + 1] = lis[j]
                    index = j  # 空出来的这个位置 待插入元素的归宿
                else:
                    break
            lis[index] = temp
    return lis


def bubble_sort(lis):
    """
    冒泡排序思路：每趟确定一个元素在最终位置 下一轮比较范围动态变化
    """
    n = len(lis)
    for index in range(n):
        flag = True
        for j in range(1, n - index):
            if lis[j - 1] > lis[j]:
                lis[j - 1], lis[j] = lis[j], lis[j - 1]
                flag = False
        if flag:
            return lis
    return lis


@timer
def select_sort(lis):
    """
    简单选择排序 每次选择一个最小的添加到有序序列
    """
    n = len(lis)
    for i in range(0, n):
        min = i
        for j in range(i + 1, n):
            if lis[j] < lis[min]:
                min = j  # 这个for循环 找到i+1到n中最小的值的下标
        lis[min], lis[i] = lis[i], lis[min]  # time: 9.5367431640625e-07
    return lis


if __name__ == '__main__':
    lis = list(range(1000))[::-1]
    # print(lis)
    print(select_sort(lis))

查找

顺序查找 折半查找

排序

插入排序

简单选择排序

冒泡排序

顺序查找折半查找