用Python实现插入排序、归并排序、睡眠排序

插入排序

插入排序（insertion sort）
该方法每趟考查列表中的每一项，将其插入新列表，使得这个新列表是排好序的。

代码包括两个部分：

• 插入部分，执行将文件插入新列表中的简单任务；
• 排序部分，重复执行插入操作，直到完成排序任务。

def insert_element(sorted_list, element):
    """
    将一个元素插入到已经排序的列表中，使列表保持有序。

    参数:
    sorted_list (list): 已排序的列表。
    element (int): 要插入的元素。

    返回值:
    list: 插入元素后的新排序列表。
    """
    # 初始化检查位置为列表的最后一个索引
    check_position = len(sorted_list) - 1

    # 初始化插入位置为0
    insert_position = 0

    # 逆序检查元素插入位置
    while check_position >= 0:
        # stepcounter += 1
        if element > sorted_list[check_position]:
            insert_position = check_position + 1
            break
        check_position -= 1

    # 在确定的位置插入元素
    sorted_list.insert(insert_position, element)
    return sorted_list


def insertion_sort(unsorted_list):
    """
    使用插入排序算法对无序列表进行排序。

    参数:
    unsorted_list (list): 无序列表。

    返回值:
    sorted_list: 排序后的列表。
    """
    sorted_list = []  # 初始化一个空的有序列表
    while len(unsorted_list) > 0:
        element_to_insert = unsorted_list.pop(0)  # 取出无序列表的第一个元素
        sorted_list = insert_element(sorted_list, element_to_insert)  # 插入到有序列表中
    return sorted_list


# 示例使用
if __name__ == '__main__':
    unsorted_list = [8, 4, 6, 1, 2, 5, 3, 7]
    sorted_list = insertion_sort(unsorted_list)
    print(sorted_list)

[1, 2, 3, 4, 5, 6, 7, 8] 

归并排序

归并排序（merge sort）比插入排序快得多。与插入排序一样， 归并排序包含两个部分：

• 合并两个列表；
• 重复利用合并来完成排序。

import math


def merging(left, right):
    """
    将两个有序列表left和right合并为一个新的有序列表new_array
    """
    new_array = []
    while left and right:
        if left[0] <= right[0]:
            new_array.append(left.pop(0))
        else:
            new_array.append(right.pop(0))
    new_array.extend(left or right)
    return new_array


def mergesort(array):
    """
    递归地将列表array分成两半，并对每一半进行排序
    然后合并已排序的部分以生成新的有序列表
    """
    if len(array) <= 1:
        return array
    mid = math.floor(len(array) / 2)
    left = mergesort(array[:mid])
    right = mergesort(array[mid:])
    return merging(left, right)


if __name__ == '__main__':
    test_array = [3, 1, 9, 0, 6, 13, 16, 2, 9, 7, 3, -4, 2, 5, -9]
    new_array = mergesort(test_array)
    print(new_array)

[-9, -4, 0, 1, 2, 2, 3, 3, 5, 6, 7, 9, 9, 13, 16] 

睡眠排序

 在Python中睡眠排序实现方法如下：

• 导入threading模块，为列表中的每个元素创建不同的计算机进程，休眠，然后插入它自己。
• 导入time.sleep模块，为不同的“线程”设置适当的睡眠时间长度。

import threading
from time import sleep

# 创建锁对象，用于确保对sorted_list的线程安全访问
lock = threading.Lock()
sorted_list = []


def sleep_sort(value):
    """
    使用休眠排序法对给定的值进行排序
    每个线程休眠时间等于其数值，然后将其添加到排序列表中
    """
    sleep(value)
    with lock:  # 确保对共享资源的线程安全访问
        sorted_list.append(value)


items = [2, 4, 5, 2, 1, 7]
threads = []

# 为每个元素创建并启动一个线程
for value in items:
    thread = threading.Thread(target=sleep_sort, args=(value,))
    thread.start()
    threads.append(thread)

# 等待所有线程完成
for thread in threads:
    thread.join()

print(sorted_list)

[1, 2, 2, 4, 5, 7] 

原文地址：https://blog.csdn.net/weixin_74254879/article/details/140731371

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！