Python sort(): 快速排序列表元素

一、sort()函数的介绍

sort()是Python内置的排序函数，用于对列表进行排序，排序的方式默认是升序排列。sort()函数有如下常用参数：

• reverse：是否将列表倒序，默认为False（升序排列）
• key：用于比较的函数，例如可以按照字符串长度排序，或者按照自定义函数排序。

sort()函数的使用格式如下：

    >>> lst = [3, 1, 4, 1, 5, 9, 2, 6]
    >>> lst.sort()
    >>> print(lst)
    [1, 1, 2, 3, 4, 5, 6, 9]

二、快速排序算法

快速排序是一种比较高效的排序算法，其基本思想是选定一个基准元素，将列表中所有小于基准元素的元素放置在基准元素的左边，将所有大于基准元素的元素放置在其右边，然后对左右两个子列表分别进行递归排序，最终得到一个有序列表。

快速排序的时间复杂度为O(nlogn)，是一种常用的排序算法。

三、用sort()函数实现快速排序

虽然Python内置了sort()函数，但如果想要自己实现快速排序算法，也是可以的。下面是利用sort()函数实现快速排序的代码示例：

    def quicksort(lst):
        if len(lst) <= 1:
            return lst
        pivot = lst[0]  # 选取第1个元素作为基准值
        left = [x for x in lst[1:] if x < pivot]
        right = [x for x in lst[1:] if x >= pivot]
        return quicksort(left) + [pivot] + quicksort(right)
    
    lst = [3, 1, 4, 1, 5, 9, 2, 6]
    lst = quicksort(lst)
    print(lst)

代码中定义了一个名为quicksort()的函数，用于实现快速排序。函数的参数是一个列表lst，函数首先判断列表长度是否小于等于1，如果是，则直接返回原列表。否则，选取列表第1个元素作为基准值pivot，将列表中所有小于基准值的元素放在left列表中，所有大于等于基准值的元素放在right列表中，最后将排序好的left列表、基准值、排序好的right列表拼接在一起，返回一个有序列表。

四、sort()函数的应用例子

例1：对字典列表按照某个键的取值进行排序

    persons = [{'name': 'Alice', 'age': 25},
               {'name': 'Bob', 'age': 18},
               {'name': 'Chris', 'age': 22},
               {'name': 'David', 'age': 30}]
               
    sorted_persons = sorted(persons, key=lambda x: x['age'])
    # 或
    persons.sort(key=lambda x: x['age'])
    
    print(sorted_persons)
    # 或
    print(persons)

上述代码中，首先定义了一个字典列表persons，其中每个字典都有'name'和'age'两个键。我们需要按照'age'键的取值对列表进行排序。使用sorted()函数并传递key参数作为排序关键字，或调用sort()函数并传递key参数即可。

例2：对字符串列表按照字符串长度排序

    words = ['apple', 'pear', 'banana', 'orange']
    
    sorted_words = sorted(words, key=lambda x: len(x))
    # 或
    words.sort(key=lambda x: len(x))
    
    print(sorted_words)
    # 或
    print(words)

上述代码中，我们需要按照字符串长度对字符串列表进行排序，同样使用sorted()函数并传递key参数作为排序关键字，或调用sort()函数并传递key参数即可。

五、总结

sort()函数是Python内置的排序函数，它可以用于对列表中元素进行排序，同时支持升序和降序排列，以及对自定义函数的应用。快速排序算法是一种高效的排序方法，其时间复杂度为O(nlogn)，我们可以利用sort()函数来进行快速排序的实现。