Python中的“sorted”函数及其实现排序列表

在Python中，sorted函数是一个非常方便的函数，它可以用来对列表进行排序。sorted函数的使用非常简单，只需调用该函数并传入待排序的列表即可。下面我们来探讨一下sorted函数的相关知识。

1. 排序列表

在Python中，我们可以使用sort函数和sorted函数来对列表进行排序。sort函数是在原地对列表进行排序，不会返回一个新的已排序的列表。sorted函数则会返回一个新的已排序的列表。

示例代码如下：

lst = [4, 2, 7, 1, 9]
lst.sort()
print(lst)  # [1, 2, 4, 7, 9]

lst = [4, 2, 7, 1, 9]
new_lst = sorted(lst)
print(new_lst)  # [1, 2, 4, 7, 9]

可以发现，lst.sort()会直接修改lst，而sorted(lst)不会改变原列表，而是返回一个新的已排序的列表。

2. sorted函数的使用

sorted函数的使用非常简单，只需传入待排序的列表即可。如果想要按照指定的方式进行排序，则可以传入一个key函数，key函数接受一个参数并返回一个值，用来决定元素的排序方式。

示例代码如下：

lst = [(1, 2), (2, 1), (3, 4), (4, 3)]
new_lst = sorted(lst, key=lambda x: x[1])
print(new_lst)  # [(2, 1), (1, 2), (4, 3), (3, 4)]

可以看到，我们使用了一个lambda表达式来指定排序方式。这里我们按照元组的第二个元素进行排序。

3. sorted函数的实现

当我们使用sorted函数对列表进行排序时，其实sorted函数是使用一种称为“归并排序”的算法来排序的。

归并排序是一种典型的分治算法，它的基本思想是将待排序的序列分成两个子序列，对子序列进行归并排序，然后再将两个已排序的子序列合并成一个有序的序列。

归并排序的具体实现可以参考下面的代码：

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

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)

lst = [4, 2, 7, 1, 9]
new_lst = merge_sort(lst)
print(new_lst)  # [1, 2, 4, 7, 9]

在这段代码中，我们定义了一个merge函数，用来将两个已排序的子序列合并成一个有序的序列。然后定义了一个merge_sort函数，用来将待排序的序列拆分成两个子序列，并对子序列进行归并排序，最后将两个已排序的子序列合并成一个有序的序列。

以上就是sorted函数及其排序列表的详细介绍，欢迎大家学习。