概念

概念:

排序:使一段数据按照升序或者降序排列
排序算法:让它得到升序或者降序排列的方式方法
稳定性算法:排序后相同元素的相对位置不发生改变
不稳定排序算法包括:选择-快速-希尔-堆排序
稳定排序算法包括:冒泡-插入-归并-基数

下面会给大家演示4中比较常规的排序算法:冒泡-插入-选择-快速

以下是四种排序算法的适用场景总结：
1. 冒泡排序（Bubble Sort）
适用场景：
数据量较小。
数据基本有序（接近排序完成的状态）。
实现简单，适合教学或调试用途。
2. 插入排序（Insertion Sort）
适用场景：
数据量较小。
数据部分有序（如在线算法中逐步添加新元素）。
对稳定性有要求的场景。
3. 选择排序（Selection Sort）
适用场景：
数据量较小。
内存空间受限（原地排序）。
不关心稳定性。
4. 快速排序（Quick Sort）
适用场景：
数据量较大。
需要高效排序（平均时间复杂度为 O(n log n)）。
不要求稳定性，但追求性能。
每种算法都有其特点和局限性，选择时需根据具体需求权衡。

5.sort方法:

sort 方法是 Python 列表对象的一个内置方法，用于对列表进行原地排序。

sort 是原地排序，直接修改原列表，不返回新列表。
其他排序方法（如 sorted()）会返回一个新的已排序列表，原列表保持不变。

sort 仅适用于列表（list 类型）。
其他排序方法（如 sorted()）可作用于任意可迭代对象（如元组、字符串等）。

sort 返回 None，因为它直接修改原对象。
sorted() 返回一个新的排序后的列表。

优势:

底层使用 Timsort 算法，对部分有序数据有很好的优化效果，平均时间复杂度为 O(n log n)。

冒泡排序

# 1. 冒泡排序（Bubble Sort）
# 原理： 重复遍历待排序序列，比较相邻元素，若顺序错误则交换位置。每一轮遍历会将最大值“冒泡”到末尾。
# 时间复杂度：
# 最坏情况：O(n²)
# 最好情况（已排序）：O(n)
# 平均情况：O(n²)
# 是否稳定：是
# 外层循环的 -1的作用: 减少比较的轮数，提高效率
# 内层循环的 -1的作用: 为了防止索引 越界
# 内层循环的 -i的作用: 减少每轮比较的次数，提高效率
# 亮点:可用count判断提前结束排序循环
def bubble_sort(arr):
    """
    冒泡排序实现
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    # 外层循环控制遍历轮数
    for i in range(n - 1):
        count = 0
        # 内层循环进行相邻元素比较和交换
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # 如果前一个元素大于后一个，则交换
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                count += 1
        if count == 0:  # 如果某一轮count不变,代表排序提前完成
            break
    return arr


# 示例调用
arr1 = [64, 34, 25, 12, 22, 11, 90]
print("冒泡排序结果:", bubble_sort(arr1))

快速排序

# 2. 快速排序（Quick Sort）
# 原理： 采用分治法策略，选取一个基准元素（pivot），将数组划分为两部分：小于基准的部分和大于基准的部分，递归地对两部分继续排序。
# 时间复杂度：
# 最坏情况：O(n²)（当每次划分极不平衡时）
# 最好情况：O(n log n)
# 平均情况：O(n log n)
# 是否稳定：否
def quick_sort(arr):
    """
    快速排序实现
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    if len(arr) <= 1:
        return arr  # 基线条件：长度为0或1时直接返回

    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    left = [x for x in arr if x < pivot]  # 小于基准的元素
    middle = [x for x in arr if x == pivot]  # 等于基准的元素, 基准元素的重复处理机制
    right = [x for x in arr if x > pivot]  # 大于基准的元素

    # 递归排序并合并结果
    return quick_sort(left) + middle + quick_sort(right)


# 示例调用
arr = [64, 34, 25, 12, 12, 22, 11, 90]
print("快速排序结果:", quick_sort(arr))

插入排序

# 3. 插入排序（Insertion Sort）
# 原理： 将数组分为已排序部分和未排序部分，依次从未排序部分取出元素，在已排序部分找到合适的位置插入。
# 时间复杂度：
# 最坏情况：O(n²)
# 最好情况（已排序）：O(n)
# 平均情况：O(n²)
# 是否稳定：是
def insertion_sort(arr):
    """
    插入排序实现
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    for i in range(1, len(arr)):
        # 从1开始代表:索引为1的元素是已排序的
        key = arr[i]  # 当前待插入的元素key
        j = i - 1  # 已排序部分的最后一个元素索引
        # 向前查找插入位置
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 元素向后移动
            j -= 1
        arr[j + 1] = key  # 插入元素, j+1 是插入位置
    return arr


# 示例调用
arr1 = [64, 34, 25, 12, 22, 11, 90]
print("插入排序结果:", insertion_sort(arr1))

选择排序

# 4. 选择排序（Selection Sort）
# 原理： 每次从未排序部分选出最小元素，放到已排序部分的末尾。
# 时间复杂度：
# 所有情况均为 O(n²)，因为无论输入如何都需要完全遍历。
# 是否稳定：否
def selection_sort(arr):
    """
    选择排序实现
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n-1):
        min_index = i  # 假设当前位置是最小值索引
        # 在剩余未排序部分寻找更小的元素
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 交换当前元素与最小元素
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

二分查找(递归)

"""
案例: 演示二分查找, 递归版.

二分查找:
    概述:
        属于查找类算法, 相对效率比较高, 时间复杂度为: O(log n)
    前提:
        列表必须是有序的.
    原理: 假设列表是 升序 的
        1. 比较 要查找的元素 和 列表的中值, 如果一样就返回True, 程序结束.
        2. 如果 要查找的元素 比 中值小, 去前半段(中值前) 查找.
        3. 如果 要查找的元素 比 中值大, 去后半段(中值后) 查找.
        4. 重复上述动作, 直至找完. 如果都找完了, 还找不到, 就返回 False
"""

# 1. 定义函数 binary_search_recursion(), 表示: 二分查找, 递归版.
def binary_search_recursion(my_list, target):
    """
    该函数是 二分查找的递归版, 实现查找指定元素是否在列表中.
    :param my_list: 待查找的列表
    :param target: 要查找的元素
    :return: True:在, False:不在
    """
    # 1.1 获取列表的长度.
    n = len(my_list)
    # 1.2 判断列表是否为空.
    if n == 0:
        return False
    # 1.3 获取列表的 中值(的索引)
    mid = n // 2
    # 1.4 比较 要查找的元素 和 中值.
    if my_list[mid] == target:
        return True
    elif target < my_list[mid]:
        # 1.5 如果要查找的元素 比 中值小, 去前半段(中值前) 查找, 递归调用.
        return binary_search_recursion(my_list[:mid], target)
    else:
        # 1.6 如果要查找的元素 比 中值大, 去后半段(中值后) 查找, 递归调用.
        return binary_search_recursion(my_list[mid + 1:], target)

    # 1.7 走到这里, 说明列表都遍历完了, 还没找到, 返回False
    return False

二分查找(非递归)

# 2. 定义函数 binary_search(), 表示: 二分查找, 非递归版.
def binary_search(my_list, target):
    # 1. 定义变量start, end 分别表示列表的开始 和 结束索引.
    start = 0
    end = len(my_list) - 1

    # 2. 循环查找, 只要条件满足就一直找.
    while start <= end:
        # 3. 计算中间值的 索引.
        mid = (start + end) // 2
        # 4. 比较 要查找的元素 和 中值.
        if my_list[mid] == target:
            return True
        elif target < my_list[mid]:
            # 5. 如果要查找的元素 比 中值小, 去前半段(中值前) 查找. 即: 修改end的值.
            end = mid - 1
        else:
            # 6. 如果要查找的元素 比 中值大, 去后半段(中值后) 查找. 即: 修改start的值.
            start = mid + 1
    # 7. 走到这里, 说明列表都遍历完了, 还没找到, 返回False
    return False