当前位置 : 主页 > 编程语言 > python >

如何用Python实现归并排序

来源:互联网 收集:自由互联 发布时间:2023-07-30
归并排序是一种经典的排序算法,其核心思想是将待排序数组分成若干个子数组,对这些子数组进行排序,最后再将排好序的子数组合并成一个有序数组。归并排序是一种效率较高的排

归并排序是一种经典的排序算法,其核心思想是将待排序数组分成若干个子数组,对这些子数组进行排序,最后再将排好序的子数组合并成一个有序数组。归并排序是一种效率较高的排序算法,其时间复杂度为O(nlogn)。

在本文中,我们将讲解如何用Python实现归并排序。

  1. 实现归并排序的思路

归并排序的实现思路包括两个部分,分别是分治和合并。具体实现步骤如下:

1)将待排序数组不断一分为二,递归地对左右两部分进行排序;

2)将排好序的左右两部分合并成一个有序数组。

  1. 用Python实现分治

分治是归并排序的核心思想,我们需要先实现分治的部分。

代码如下:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

在这个函数中,我们首先判断如果数组长度小于等于1,则直接返回该数组。否则,我们需要将该数组一分为二,分别对左右两部分进行递归排序,最后再将排好序的左右两部分合并起来。

2.1 实现合并

在实现分治的基础上,我们需要实现合并的部分。

代码如下:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

在这个函数中,我们先初始化指针i和j,分别指向左右两部分要比较的元素。接着我们不断比较左右两部分元素,将较小的元素添加到结果列表中,并将该指针右移。最后,我们还要将剩下的所有元素添加到结果列表中,以便最终得到排好序的数组。

  1. 完整代码

将分治和合并部分组合起来,得到完整代码如下:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result
  1. 测试

为了验证我们的归并排序代码是否正确,我们需要进行测试。

代码如下:

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

输出结果为:

[1, 2, 3, 4, 5, 6, 7, 8]

测试结果表明,我们的归并排序代码是正确的。

上一篇:Python中的数据可视化库seaborn详解
下一篇:没有了
网友评论