插入排序
插入排序(insertion sort)
该方法每趟考查列表中的每一项,将其插入新列表,使得这个新列表是排好序的。代码包括两个部分:
- 插入部分,执行将文件插入新列表中的简单任务;
- 排序部分,重复执行插入操作,直到完成排序任务。
def insert_element(sorted_list, element):"""将一个元素插入到已经排序的列表中,使列表保持有序。参数:sorted_list (list): 已排序的列表。element (int): 要插入的元素。返回值:list: 插入元素后的新排序列表。"""# 初始化检查位置为列表的最后一个索引check_position = len(sorted_list) - 1# 初始化插入位置为0insert_position = 0# 逆序检查元素插入位置while check_position >= 0:# stepcounter += 1if element > sorted_list[check_position]:insert_position = check_position + 1breakcheck_position -= 1# 在确定的位置插入元素sorted_list.insert(insert_position, element)return sorted_listdef 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 mathdef 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_arraydef mergesort(array):"""递归地将列表array分成两半,并对每一半进行排序然后合并已排序的部分以生成新的有序列表"""if len(array) <= 1:return arraymid = 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]