Python内置排序算法与常用排序算法

在Python中，内置的排序算法主要有两种：sort()和sorted()函数。sort()函数会直接修改原列表，而sorted()函数则会返回一个新的排序列表，不会修改原列表。这两个函数都接受一个可选的参数“reverse”，默认为False，表示升序排序，如果为True，则表示降序排序。
除了内置的排序算法外，Python还提供了多种常用的排序算法，下面将逐一介绍它们的原理、实现方式和在Python中的使用方法。

1. 冒泡排序
   冒泡排序是一种简单的排序算法，通过不断比较相邻元素的大小，并进行交换，使得较大的元素逐渐“冒泡”到列表的末尾。冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
   在Python中，可以使用以下代码实现冒泡排序：

   def bubble_sort(lst):
   n = len(lst)
   for i in range(n):    # 外层循环控制比较的轮数
   for j in range(0, n-i-1):   # 内层循环控制每轮比较的次数
   if lst[j] > lst[j+1]:   # 如果前一个元素大于后一个元素，则交换它们的位置
   lst[j], lst[j+1] = lst[j+1], lst[j]
   return lst

2. 选择排序
   选择排序也是一种简单的排序算法，它的基本思想是每次从未排序的元素中选出最小（或最大）的一个元素，存放到已排序序列的末尾。选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
   在Python中，可以使用以下代码实现选择排序：

   def selection_sort(lst):
   for i in range(len(lst)):   # 遍历所有未排序的元素
   min_index = i   # 记录当前未排序元素中最小的元素的索引
   for j in range(i+1, len(lst)):  # 遍历当前未排序元素之后的元素
   if lst[j] < lst[min_index]:  # 如果找到更小的元素，则更新最小元素的索引
   min_index = j
   # 将最小元素交换到已排序序列的末尾
   lst[i], lst[min_index] = lst[min_index], lst[i]
   return lst

3. 插入排序
   插入排序的基本思想是将未排序的元素插入到已排序序列的合适位置。插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
   在Python中，可以使用以下代码实现插入排序：

   def insertion_sort(lst):
   for i in range(1, len(lst)):   # 从第二个元素开始遍历未排序的元素
   key = lst[i]
   j = i-1   # 记录已排序序列中未比较的元素的索引
   while j >=0 and key < lst[j] :  # 如果当前元素小于已排序序列中的元素，则将已排序序列中的元素后移一位
   lst[j+1] = lst[j]
   j -= 1
   # 将当前元素插入到已排序序列的合适位置
   lst[j+1] = key
   return lst

4. 快速排序（QuickSort）
   快速排序是一种基于分治思想的排序算法，它的基本思想是选择一个基准元素，将比基准元素小的元素移动到其左边，比基准元素大的元素移动到其右边，然后对左右两边的子序列递归进行此操作。快速排序的时间复杂度在最坏情况下为O(n^2)，但平均情况下为O(nlogn)，空间复杂度为O(logn)。