博客

python实现归并排序算法

  • Post category:Python

Python实现归并排序算法攻略

归并排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，具有稳定性和适用于数据量的优点。在本篇攻略中，我们将详细讲解Python实现归并排序算法的过程和示例。

基本思路

归并排序的基本思路是将一个大的序列分成两子序列，然后对这两个子序列分别进行排序最后将两个有序的子序列合并成一个有序的序。具体步骤如下：

  1. 将序列分成两个子序列，直到每个子序列只有一个元素。
  2. 对每个子序列进行排序。
  3. 将两个有序的子序列合并成一个有序的序列。

Python实现

下面Python实现归并排序算法的代码：

def merge_sort(lst):
    if(len(lst)) <= 1:
        return lst
    mid = len(lst) // 2
    left_lst = lst[:mid]
    right_lst = lst[mid:]
    left_lst = merge_sort(left_lst)
    right_lst = merge_sort(right_lst)
    return merge(left_lst, right_lst)

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

在这个例子中，我们首先定义了一个函数merge_sort()，它接受一个列表作为参数。如果列表的长度小于等于1，则直接返回该列表。否则，我们将列表分成两个子列表，分别对这两个子列表进行排序，然后将它们合并成一个有序的列表。

我们使用merge()函数来合并两个有序的子列表。在merge()函数中，我们定义了一个空列表result，以及两个指针i和j，分别指向左子列表和右子列表的第一个元素。我们比较左子列表和右子列表的第一个元素，将较小的元素添加到result列表中，并将指针向后移动一位。当其中一个子列表的元素全部添加到result列表中后，我们将另一个子列表的剩余元素添加到result列表中。

示例一：对整数列表进行排序

下面是一个示例，演示了如何使用merge_sort()函数对一个整数列表进行排序：

lst = [3, 1, 4, 2, 5]
sorted_lst = merge_sort(lst)
print(sorted_lst) # 输出 [1, 2, 3, 4, 5]

在这个例子中，我们首先定义了一个整数列表lst，然后使用merge_sort()函数对它进行排序，并将排序后的结果赋值给sorted_lst变量。最后，我们打印sorted_lst变量的值，即排序后的整数列表。

输出结果为：

[1, 2, 3, 4, 5]

示例二：对字符串列表进行排序

下面是另一个示例，演示了如何使用merge_sort()函数对一个字符串列表进行排序：

lst = ['apple', 'banana', 'orange', 'pear']
sorted_lst = merge_sort(lst)
print(sorted_lst) # 输出 ['apple', 'banana', 'orange', 'pear']

在这个例子中，我们首先定义了一个字符串列表lst，然后使用merge_sort()函数对它进行排序，并将排序后的结果赋值给sorted_lst变量。最后，我们打印sorted_lst变量的值，即排序后的字符串列表。

输出结果为：

['apple', 'banana', 'orange', 'pear']

总结

归并排序是一种常用的排序算法它的时间复杂度为O(nlogn)，具有稳定性和适用于大数据量的优点。在Python中，我们可以使用递归的实现归并排序算法。

Tags: