合并排序

合并排序

1.题目描述

题目描述：

picture 0

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。 示例 2：

输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。

2.解题思路

picture 0

合并排序动画1

合并排序动画2

3.代码实现

def apart(data):
    """ 
    合并排序法函数： 
    应该分成两部分：分离和合并排序 
    分离：将data每次对半分开，直到每个列表都只有一个元素，这里应采用递归。 
    """
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = data[:mid]
    right = data[mid:]

    left = apart(left)
    right = apart(right)
    return merge_sort(left, right)


def merge_sort(left, right):
    """ 
    排序：两两比较。 
    合并：将两两比较的结果合并起来，组成一个新的列表。再往上回溯。直到合成排好序的完整列表。 
    """
    result = []
    i = j = 0
    
    # 合并过程中统计逆序对
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            # 当 left[i] > right[j] 时，left[i] 及其后面的所有元素都大于 right[j]
            # 因此产生 len(left) - i 个逆序对
            
            j += 1
    
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    return result


data = [5, 4, 2, 6, 3, 1]
print("原始数据为：", data)
print("-------------------------------")
print("排序之后的数据为：", apart(data))
print("-------------------------------")

def apart(data):
    """ 
    合并排序法函数： 
    应该分成两部分：分离和合并排序 
    分离：将data每次对半分开，直到每个列表都只有一个元素，这里应采用递归。 
    """
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = data[:mid]
    right = data[mid:]

    left = apart(left)
    right = apart(right)
    return merge_sort(left, right)


def merge_sort(left, right):
    """ 
    排序：两两比较。 
    合并：将两两比较的结果合并起来，组成一个新的列表。再往上回溯。直到合成排好序的完整列表。 
    """
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result


data = [5,2,3,0]
print("原始数据为：", data)
print("-------------------------------")
print("排序之后的数据为：", apart(data))
print("-------------------------------")