Python 排序与查找算法

时间：2025-01-20 13:37:10

Python 语言实现几种不同的排序算法，以及二分查找算法，排序算法是计算机科学中重要的基础算法之一，用于将一组数据按照指定的顺序进行排列。本文将介绍Python语言实现的几种常见的排序算法，以及二分查找算法的原理和实现。

排序算法

该代码段实现了一些常见的排序算法，并通过装饰器函数cal_time计算了它们的运行时间。

以下是代码中涉及的排序算法：

  1. 冒泡排序（bubble_sort）：通过比较相邻元素的大小，依次将最大的元素移到列表末尾。

  2. 优化的冒泡排序（bubble_sort_1）：在冒泡排序的基础上进行了优化，增加了一个标志位来判断列表是否已经有序，如果有序则提前结束排序。

  3. 选择排序（select_sort）：每次从未排序的部分选择最小的元素放到已排序部分的末尾。

  4. 插入排序（insert_sort）：将待排序元素插入到已排序部分的合适位置。

  5. 快速排序（quick_sort）：选取一个基准值，将小于基准值的元素放在其左边，大于基准值的元素放在右边，然后递归地对左右两部分进行快速排序。

  6. 系统排序（sys_sort）：使用Python内置的排序方法对列表进行排序。

  7. 堆排序（heap_sort）：将列表构建成一个大顶堆，然后依次将堆顶元素（最大值）与末尾元素交换，并重新调整堆结构。

此外，代码还使用了copy模块中的deepcopy函数来复制列表，以保证每个排序算法使用的是相同的原始数据。

在代码的最后，通过调用这些排序函数对已经排好序的列表进行排序，以比较它们的运行时间。

请注意，代码中的@cal_time是一个装饰器，用于计算函数的运行时间。它会将被装饰的函数作为参数传递给cal_time函数，并返回一个新的函数，该新函数在调用被装饰的函数之前和之后计时并输出运行时间。这样，在调用排序函数时，会打印出排序算法的运行时间。

import random
import time
import copy
import sys

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

@cal_time
def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

@cal_time
def bubble_sort_1(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:
            break

def select_sort(li):
    for i in range(len(li) - 1):
        min_loc = i
        for j in range(i+1,len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j+1]=li[j]
            j = j - 1
        li[j + 1] = tmp


def quick_sort_x(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort_x(data, left, mid - 1)
        quick_sort_x(data, mid + 1, right)

def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left


@cal_time
def quick_sort(data):
    return quick_sort_x(data, 0, len(data) - 1)

@cal_time
def sys_sort(data):
    return ()

def sift(data, low, high):
    i = low
    j = 2 * i + 1
    tmp = data[i]
    while j <= high: #只要没到子树的最后
        if j < high and data[j] < data[j + 1]:
            j += 1
        if tmp < data[j]:#如果领导不能干
            data[i] = data[j] #小领导上位
            i = j
            j = 2 * i + 1
        else:
            break
    data[i] = tmp

def heap_sort(data):
    n = len(data)
    for i in range(n // 2 - 1, -1, -1):
        sift(data, i, n - 1)
        for i in range(n - 1, -1, -1):
            data[0], data[i] = data[i], data[0]
            sift(data, 0, i - 1)

(100000)
data = list(range(1000, 1, -1))
()
#(data)
data1 = (data)
data2 = (data)
data3 = (data)

bubble_sort(data1)
quick_sort(data2)
sys_sort(data3)

查找算法

该代码段实现了两个二分查找算法，并使用装饰器函数cal_time计算它们的运行时间。

以下是代码中涉及的函数：

  1. cal_time装饰器函数：计算被装饰函数的运行时间。它会记录函数开始执行的时间（t1），执行被装饰函数，然后记录函数结束执行的时间（t2），计算并打印函数的运行时间。

  2. bin_search函数：使用循环实现的二分查找算法。给定一个有序的数据集（data_set）和目标值（val），在数据集中查找目标值的索引。

  3. binary_search函数：使用递归实现的二分查找算法。给定一个有序的数据集（dataset）和目标值（find_num），在数据集中查找目标值并返回。

  4. binary_search_alex函数：通过调用binary_search函数来实现二分查找，并使用装饰器cal_time计算运行时间。

  5. random_list函数：生成随机数据列表，用于测试二分查找算法。

在代码的最后，通过调用bin_search和binary_search_alex函数来测试二分查找算法，并打印出查找结果和运行时间。

请注意，代码中的@cal_time是一个装饰器，用于计算函数的运行时间。它会将被装饰的函数作为参数传递给cal_time函数，并返回一个新的函数，该新函数在调用被装饰的函数之前和之后计时并输出运行时间。这样，在调用二分查找函数时，会打印出算法的运行时间。

import time
import random

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

@cal_time
def bin_search(data_set, val):
    low = 0
    high = len(data_set) - 1
    while low <= high:
        mid = (low+high)//2
        if data_set[mid]['id'] == val:
            return mid
        elif data_set[mid]['id'] < val:
            low = mid + 1
        else:
            high = mid - 1
    return


def binary_search(dataset, find_num):
    if len(dataset) > 1:
        mid = int(len(dataset) / 2)
        if dataset[mid] == find_num:
            #print("Find it")
            return dataset[mid]
        elif dataset[mid] > find_num:
            return binary_search(dataset[0:mid], find_num)
        else:
            return binary_search(dataset[mid + 1:], find_num)
    else:
        if dataset[0] == find_num:
            #print("Find it")
            return dataset[0]
        else:
            pass
            #print("Cannot find it.")

@cal_time
def binary_search_alex(data_set, val):
    return binary_search(data_set, val)

def random_list(n):
    result = []
    ids = list(range(1001,1001+n))
    a1 = ['zhao','qian','sun','li']
    a2 = ['li','hao','','']
    a3 = ['qiang','guo']
    for i in range(n):
        age = (18,60)
        id = ids[i]
        name = (a1)+(a2)+(a3)

data = list(range(100000000))
print(bin_search(data, 173320))
print(binary_search_alex(data, 173320))

相关文章