py 排序

Python提供了很多排序算法，包括内置函数sorted()和list.sort()方法，以及常见的冒泡排序、选择排序、插入排序、快速排序等。

1. 内置函数sorted()：sorted()函数可以对列表、元组、字符串等进行排序，返回一个新的排序后的列表，原列表不变。例如：

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_lst = sorted(lst)
print(sorted_lst) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

2. list.sort()方法：list.sort()方法可以对列表进行原地排序，即直接修改原列表，不返回新的列表。例如：

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

3. 冒泡排序：冒泡排序是一种简单的排序算法，它重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误就交换位置，直到没有任何一对数字需要交换。例如：

def bubble_sort(lst):
    n = len(lst)
    for i in range(n-1):
        for j in range(n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
bubble_sort(lst)
print(lst) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

4. 选择排序：选择排序是一种简单直观的排序算法，它的基本思想是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。例如：

def selection_sort(lst):
    n = len(lst)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
selection_sort(lst)
print(lst) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

5. 插入排序：插入排序是一种简单直观的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如：

def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        temp = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > temp:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = temp

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
insertion_sort(lst)
print(lst) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

6. 快速排序：快速排序是一种高效的排序算法，它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。例如：

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    left = [x for x in lst[1:] if x < pivot]
    right = [x for x in lst[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lst = quick_sort(lst)
print(lst) # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]