归并排序

使用分治的思想实现。

算法原理

归并排序采用经典的分治算法，将问题分成一些小的问题，然后递归求解，治的阶段就是将分的阶段的答案修补在一起，分而治之。

import random
import time

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    i = 0  # 左半部分的索引
    j = 0  # 右半部分的索引

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    while i < len(left):
        merged.append(left[i])
        i += 1

    while j < len(right):
        merged.append(right[j])
        j += 1

    return merged
#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time = time.time()
merge_sort(myList)
print(myList)
print(f"Time taken: {time.time() - start_time}")

Time taken: 0.06033492088317871

复杂度分析