归并排序-Python

归并,排序,python · 浏览次数 : 41

小编点评

**归并排序的时间复杂度：O(nlogn)，空间复杂度为O(n)** **步骤：** 1. **合并两个有序数组**（`def merge(left_array, right_array)`） - 两个数组的长度分别为 `len(left_array)` 和 `len(right_array)` - 创建一个新的空数组 `merge_array` - 两个指针 `left_index` 和 `right_index` 指向 `left_array` 和 `right_array` 的首地址 - 循环比较两数组的元素，并将较小的元素添加到 `merge_array` 中 - 继续向 `merge_array` 中添加元素直到其中一个数组为空 2. **递归排序左右数组**（`def merge_sort(array)`） - 如果 `array` 的长度为 1，则视为已排序，返回 - 否则，将 `array` 分为左右两半 - 递归地排序左右两个子数组 3. **合并排序结果**（`def merge(left_array, right_array)`） - 创建一个新的空数组 `res` - 两个指针 `left_index` 和 `right_index` 指向 `left_array` 和 `right_array` 的首地址 - 循环比较两数组的元素，并将较小的元素添加到 `res` 中 - 继续向 `res` 中添加元素直到其中一个数组为空 **时间复杂度分析：** - 合并两个数组：`O(nlogn)`，其中 `n` 是数组的长度 - 递归排序左右数组：`O(nlogn)` - 合并排序结果：`O(n)` **空间复杂度分析：** - 合并两个数组：`O(n)` - 递归排序左右数组：`O(n)` - 合并排序结果：`O(n)` **代码示例：** ```python def merge(left_array, right_array): left_index, right_index, merge_array = 0, 0, list() while left_index < len(left_array) and right_index < len(right_array): if left_array[left_index] <= right_array[right_index]: merge_array.append(left_array[left_index]) left_index += 1 else: merge_array.append(right_array[right_index]) right_index += 1 merge_array = merge_array + left_array[left_index:] + right_array[right_index:] return merge_array ```

正文

归并排序的时间复杂度O（nlogn），空间复杂度为O（n）

首先我们先假设有两个有序数组，我们去进行一次归并

用代码实现

def merge(li: list, start: int, mid: int, end: int) :
    res=[]
    j = mid +1
    while start <= mid and j <= end:
        if li[start] < li[j]:
            res.append(li[start])
            start +=1
        else:
            res.append(li[j])
            j +=1
    #运行到这一步，说明左右两边一定有一遍已经下标已经超了，即一定有一遍数字已经没了
    #然后判断如果是左边还有数字就把左边剩下的数字全部插入列表中，无需在做判断
    #判断如果是右边还有数字就把左边剩下的数字全部插入列表中，无需在做判断
    while start <= mid:
        res.append(li[start])
        start +=1
    while j <= end:
        res.append(li[j])
        j +=1
    
    return res

最后交给递归

def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    return merge(left_array, right_array)


def merge(left_array, right_array):
    left_index, right_index, merge_array = 0, 0, list()
    while left_index < len(left_array) and right_index < len(right_array):
        if left_array[left_index] <= right_array[right_index]:
            merge_array.append(left_array[left_index])
            left_index += 1
        else:
            merge_array.append(right_array[right_index])
            right_index += 1
    merge_array = merge_array + left_array[left_index:] + right_array[right_index:]
    return merge_array