排序

冒泡排序

冒泡排序的时间复杂度是$O(n^2)$（最好的情况下的时间复杂度是$O(n)$），空间复杂度是$O(1)$

• 是一个稳定的排序方式

• 通过交换相邻数字实现

快速排序

快速排序的平均时间复杂度是$O(nlogn)$（最好的情况下的时间复杂度是$O(nlongn)$），最坏的情况下，可退化成$O(n^2)$（少见）

空间复杂度是$O(nlogn)$​

• 它是一个不稳定的排序算法
• 通过大于\小于的传递性实现

一般情况下，我们取数组的第一个数作为基准进行快速排序。在第一步中，基准数为5。可以看出，在第二行的数组中，比5小的元素：3、4、1、2，都被置于5的左侧，而比5大的元素则被置于5的右侧。

这时，元素5在有序数组中的位置就确定了。第三行中，我们再取左右两个无序数组的第一个数3和6，分别作为它们的基准数，然后再次对数组进行分拆。分拆结束之后，3和6在有序数组中的位置也确定了。

接下来，继续处理分拆出来的四个子数组：[1,2]、[4]、[]、[8,7]。其中，一个子数组只剩一个数，一个为空。这意味着[4]与[]已经完成了对自己的快速排序。而其他的两个子数组则需继续处理。全部处理完毕后，我们将得到一个完整的有序数组。

可以看出，快速排序也是通过这样的分治思想来排序的。

def quick_sort(arr):
    """
    快速排序函数，接受一个数组并对其进行原地排序。
参数:
arr (list): 需要排序的数组。
"""

def partition(low, high):
    """
    进行分区操作，选择基准，并按基准分割数组，小于基准的放左边，大于等于基准的放右边。
    
    参数:
    low (int): 考虑分区的数组部分的起始索引。
    high (int): 考虑分区的数组部分的结束索引。
    
    返回:
    int: 基准的最终位置索引。
    """
    pivot = arr[low]  # 选择列表第一个元素作为基准
    i = low + 1  # 初始化一个指针，指向基准后的第一个元素
    
    # 遍历基准之后到high的元素
    for j in range(low + 1, high + 1):
        # 如果当前元素小于基准，与i指向的元素交换，i后移
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    
    # 将基准元素放到其最终位置，i-1位置的元素与基准交换
    arr[low], arr[i - 1] = arr[i - 1], arr[low]
    return i - 1  # 返回基准的最终位置

def quick_sort_recursive(low, high):
    """
    递归排序数组的子部分。
    
    参数:
    low (int): 要排序的子数组的起始索引。
    high (int): 要排序的子数组的结束索引。
    """
    if low < high:
        pi = partition(low, high)  # 执行分区操作，并获取基准的最终位置
        quick_sort_recursive(low, pi - 1)  # 递归排序基准左边的子数组
        quick_sort_recursive(pi + 1, high)  # 递归排序基准右边的子数组

quick_sort_recursive(0, len(arr) - 1)  # 从整个数组的起始到结束位置开始排序