归并排序

一、原理

“分而治之”的思想：

• 1.先分组。
• 2.然后合并：
  • 1）定义一个临时数组，用来保存合并后的元素。
  • 2）依次比较提取最小的数。

二、代码实现

import numpy as np
from time import time

# 合并数组
def merge(arr_left, arr_right, reverse=False):
    i, j = 0, 0  # i,j分别是arr_left和arr_right的起始索引标记
    temp_list = []  # 定义一个临时数组，用来保存合并后的元素
    
    while i < len(arr_left) and j < len(arr_right):
        if reverse:  # 从大到小排序
            if arr_left[i] >= arr_right[j]:
                temp_list.append(arr_left[i])
                i += 1
            else:
                temp_list.append(arr_right[j])
                j += 1
        else:  # 从小到大排序
            if arr_left[i] <= arr_right[j]:
                temp_list.append(arr_left[i])
                i += 1
            else:
                temp_list.append(arr_right[j])
                j += 1
    if i == len(arr_left):
        temp_list.extend(arr_right[j:])
    else:
        temp_list.extend(arr_left[i:])
        
    return temp_list

# (二分)归并排序
def merge_sort(arr, reverse=False):
    if len(arr) <= 1:
        return arr
    
    index_middle = len(arr) // 2
    arr_left = merge_sort(arr[:index_middle], reverse)
    arr_right = merge_sort(arr[index_middle:], reverse)
    
    return merge(arr_left, arr_right, reverse)


if __name__ == "__main__":
    arr = [8, 9, 1, 7, 2, 3, 5, 4, 6]
    print("排序前的数组:", arr)
    sorted_arr = merge_sort(arr)  # 默认reverse=False，表示从小到大排序
    print("从小到大排序:", sorted_arr)
    sorted_arr = merge_sort(arr, reverse=True)  # 从大到小排序
    print("从大到小排序:", sorted_arr)
    
    print("----------")
    # 归并排序
    np.random.seed(10)
    array = list(np.random.randint(0, 1000, size=(2000,)))
    start = time()
    sorted_arr = merge_sort(array, reverse=False)
    end = time()
    print(f"merge_sort()函数耗时{end - start}秒")
    print(sorted_arr[:100])

运行结果：