Sort

Jessica Gracewell2023-09-282023-09-28

Sort

第一部分：排序算法概述与分类

在编程中，排序是一种基础且常用的操作。排序算法通常可以分为两大类：

比较类排序：
通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：
不通过比较来决定元素间的相对次序，可以达到线性时间复杂度。

每种排序算法都有其适用的场景和限制，选择合适的排序算法可以大大提高程序的效率。

接下来我们将逐一介绍各种排序算法，包括它们的工作原理、算法描述、Python代码实现。我们还会穿插一些典型的应用案例，以帮助大家更好地理解和掌握这些算法。

第二部分：冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

算法描述
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。
代码解读与案例

def bubble_sort(arr):
    """
    冒泡排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 外层循环负责遍历整个列表，每次遍历都会将当前最大的元素放到正确的位置
    2. 内层循环负责比较相邻元素的大小，并进行交换，确保较大的元素冒泡到列表的末尾
    3. 随着外层循环的进行，内层循环的范围逐渐缩小，因为较大的元素已经被放置到了列表的末尾
    """
    n = len(arr)  # 获取列表长度
    for i in range(n):  # 外层循环，遍历整个列表
        # 初始化标志位，用于优化。如果某一轮比较中没有发生交换，则说明列表已经有序，无需继续比较
        flag = False
        for j in range(0, n - i - 1):  # 内层循环，每次将最大的元素冒泡到末尾
            if arr[j] > arr[j + 1]:  # 比较相邻元素，如果前者大于后者，则交换位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                flag = True  # 发生了交换，将标志位设为True
        if not flag:  # 如果没有发生交换，则说明列表已经有序，退出循环
            break
    return arr


# 案例
bubble_sort_example = bubble_sort([64, 34, 25, 12, 22, 11, 90])

在实际应用中，冒泡排序由于其较高的时间复杂度，通常不适用于元素数量较多的场合。但是由于其实现简单，常常用于教学中介绍排序算法的基础知识。

第三部分：选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

算法描述
1. 初始状态：无序区为 R[1…n]，有序区为空；
2. 第i趟排序（i=1,2,3…n−1）开始时，当前有序区和无序区分别为 R[1…i−1] 和 R(i…n)。该趟排序从当前无序区中选出关键字最小的记录 R[k]；
3. 将之与无序区第一条记录 R[i] 交换，使 R[1…i] 和 R(i+1…n) 分别变为记录个数增加1的新有序区和记录个数减少1的新无序区；
4. n−1 趟结束，数组有序化了。
代码解读与案例

def selection_sort(arr):
    """
    选择排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 从未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置。
    2. 再从剩余未排序的元素中继续寻找最小（或最大）的元素，然后放到已排序序列的末尾。
    3. 重复第二步，直到所有元素均排序完毕。
    """
    n = len(arr)  # 获取列表长度
    for i in range(n):  # 外层循环，每次找到未排序的最小元素
        min_idx = i  # 假设当前位置是最小值
        for j in range(i+1, n):  # 内层循环，遍历未排序的元素
            if arr[j] < arr[min_idx]:  # 找到更小的元素
                min_idx = j  # 更新最小值的索引
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 将找到的最小值与当前位置的值交换
    return arr

# 案例
selection_sort_example = selection_sort([64, 34, 25, 12, 22, 11, 90])

通过这个例子，我们可以清晰地看到选择排序是如何工作的。在每一轮中，它都会从未排序的部分找到最小的元素，然后将其放到已排序部分的末尾。这个过程会一直持续，直到整个列表都已排序。

选择排序虽然实现简单，但由于其时间复杂度为 O(n 2)，在处理大数据集时可能不够高效。在学习和实验中使用选择排序可以帮助我们更好地理解排序算法的基础知识。

第四部分：插入排序

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述
1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。
代码解读与案例

def insertion_sort(arr):
    """
    插入排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 从第一个元素开始，认为它是已经被排序的元素。
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
    3. 如果已排序的元素大于新元素，将这个元素移到下一个位置。
    4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
    5. 插入新元素到该位置后。
    6. 重复步骤2-5。
    """
    for i in range(1, len(arr)):  # 从第二个元素开始遍历
        key = arr[i]  # 取出待排序的元素
        j = i - 1  # 从已排序的序列的最后一个元素开始比较
        # 在已排序的元素序列中从后向前扫描，找到插入位置
        while j >= 0 and key < arr[j]:  
            arr[j + 1] = arr[j]  # 如果待排序的元素小于当前元素，将当前元素后移一位
            j -= 1  # 继续与前一个元素比较
        arr[j + 1] = key  # 插入到找到的位置
    return arr

# 案例
insertion_sort_example = insertion_sort([64, 34, 25, 12, 22, 11, 90])

插入排序的时间复杂度是 O(n 2)，但它在某些场合下表现得非常高效，例如当列表已经部分排序时。由于其实现简单，适合小规模数据的排序，因此在实际应用中也经常被使用。

第五部分：希尔排序

希尔排序，也称为递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序的基本思想是将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法描述
1. 选择一个增量序列 t1,t2,…,tk，其中 ti>ti+1，且tk=1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码解读与案例

def shell_sort(arr):
    """
    希尔排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 选择一个增量序列，该序列最后必须为1，即最后一趟排序是普通的插入排序。
    2. 对于每个增量值，将数组分为若干子序列，每个子序列包含的元素数量为增量值。
    3. 对每个子序列进行插入排序。
    4. 减小增量值，重复步骤2-3，直到增量值为1。
    """
    n = len(arr)  # 获取列表长度
    # 初始增量为列表长度的一半
    gap = n // 2  
    # 当增量大于0时，继续分组进行插入排序
    while gap > 0:  
        # 对每个子序列进行插入排序
        for i in range(gap, n):  
            temp = arr[i]  # 当前待排序的元素
            j = i
            # 在当前子序列中，将大于当前元素的值都向后移动，为当前元素腾出插入的空间
            while j >= gap and arr[j - gap] > temp:  
                arr[j] = arr[j - gap]  # 元素后移
                j -= gap  # 继续比较前面的元素
            arr[j] = temp  # 插入到正确位置
        # 减小增量值，准备下一趟排序
        gap //= 2  
    return arr

# 案例
shell_sort_example = shell_sort([64, 34, 25, 12, 22, 11, 90])

第六部分：归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

算法描述
1. 将已有序的子序列合并，得到完全有序的序列；
2. 即先使每个子序列有序，再使子序列段间有序；
3. 若将两个有序表合并成一个有序表，称为二路归并。
代码解读与案例

def merge_sort(arr):
    """
    归并排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 将列表不断分解为两半，直到每个子列表只包含一个元素。
    2. 对每个子列表进行合并操作，将两个有序的子列表合并为一个有序的列表。
    3. 重复步骤2，直到得到完全排序的列表。
    """
    if len(arr) <= 1:  # 如果列表只有一个元素，则已经有序，直接返回
        return arr
    mid = len(arr) // 2  # 计算中点，将列表分为两半
    left = arr[:mid]  # 左半部分列表
    right = arr[mid:]  # 右半部分列表
    
    # 递归地将左右两半进行归并排序
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 合并两个有序列表
    return merge(left, right)


def merge(left, right):
    """
    合并两个有序列表为一个有序列表
    
    :param left: 有序列表1
    :param right: 有序列表2
    :return: 合并后的有序列表
    """
    result = []  # 存储合并后的结果
    i = j = 0  # 初始化两个列表的指针位置
    while i < len(left) and j < len(right):  # 当两个列表都有元素时
        if left[i] < right[j]:  # 将较小的元素添加到结果列表中
            result.append(left[i])
            i += 1  # 移动左列表的指针
        else:
            result.append(right[j])
            j += 1  # 移动右列表的指针
    result += left[i:]  # 添加左列表中剩余的元素
    result += right[j:]  # 添加右列表中剩余的元素
    return result

# 案例
merge_sort_example = merge_sort([64, 34, 25, 12, 22, 11, 90])

第七部分：快速排序

快速排序是一种分治的排序算法。它的基本思想是：选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法描述
1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码解读与案例

def quick_sort(arr):
    """
    快速排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 选择一个元素作为基准。
    2. 将小于基准的元素放在基准左边，大于基准的元素放在基准右边。
    3. 分别对基准左右两侧的元素进行递归排序。
    """
    if len(arr) <= 1:  # 如果列表只有一个元素，则已经有序，直接返回
        return arr
    pivot = arr[0]  # 选择第一个元素作为基准
    less = [x for x in arr[1:] if x <= pivot]  # 所有小于基准的元素
    greater = [x for x in arr[1:] if x > pivot]  # 所有大于基准的元素
    return quick_sort(less) + [pivot] + quick_sort(greater)  # 递归排序并合并

# 案例
quick_sort_example = quick_sort([64, 34, 25, 12, 22, 11, 90])

快速排序因其较高的平均性能而被广泛使用，它的平均时间复杂度为 O(nlogn)，但在最坏情况下可能会退化到 O(n 2 )。在实际应用中，通常会采用一些策略来避免最坏情况的发生，例如随机化快速排序，它会从待排序列中随机选择基准。

第八部分：堆排序

堆排序是一种基于比较的排序算法，通过利用堆这种数据结构所设计的。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

算法描述
1. 将初始待排序关键字序列 R1,R2,…,Rn构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素 R1与最后一个元素 Rn交换，此时得到新的无序区和新的有序区 R1,R2,…,Rn-1和 Rn，且满足 R1,R2,…,Rn-1≤Rn；
3. 由于交换后新的堆顶 R1可能违反堆的性质，因此需要对当前无序区 R1,R2,…,Rn-1调整为新堆，然后再次将 R1与无序区最后一个元素交换，得到新的无序区 R1,R2,…,Rn-2和新的有序区 Rn-1,Rn。不断重复此过程直到有序区的元素个数为 n−1 ，则整个排序过程完成。
代码解读与案例

def heapify(arr, n, i):
    """
    为了将给定的树转换为大顶堆，进行堆化。
    
    :param arr: 输入的列表
    :param n: 列表的长度
    :param i: 当前的根节点索引
    """
    largest = i  # 初始化最大值为根
    l = 2 * i + 1  # 左孩子 = 2*i + 1
    r = 2 * i + 2  # 右孩子 = 2*i + 2
    
    # 如果左孩子存在且大于根
    if l < n and arr[i] < arr[l]:
        largest = l
    
    # 如果右孩子存在且大于根
    if r < n and arr[largest] < arr[r]:
        largest = r
    
    # 如果最大值不是根
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)  # 递归地对影响到的子树进行堆化


def heap_sort(arr):
    """
    堆排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 构建一个最大堆
    2. 交换根节点与最后一个节点（最大元素与最后一个元素交换）
    3. 移除最后一个元素（最大元素）到有序列表
    4. 堆的大小减一，对新的根节点进行堆化
    5. 重复步骤2-4，直到堆的大小为1。
    """
    n = len(arr)
    
    # 构建大顶堆（从下往上构建）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 一个个从堆顶取出元素，放到当前堆的末尾，并调整堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)  # 堆化根节点
    
    return arr

# 案例
heap_sort_example = heap_sort([64, 34, 25, 12, 22, 11, 90])

堆排序有着稳定的 O(nlogn) 时间复杂度，并且是原地排序，不需要额外的存储空间，是一种在实际应用中非常实用的排序算法。

第九部分：计数排序

计数排序是一种非基于比较的排序算法，适用于一定范围内的整数排序。由于其运行时间依赖于数列的范围，所以它非常适合于只有固定范围内的整数的情况。

算法描述
找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。
代码解读与案例

def counting_sort(arr):
    """
    计数排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 找出待排序数组中的最大值和最小值，确定范围。
    2. 初始化一个计数数组，长度为最大值减去最小值加1，用于存储每个元素的出现次数。
    3. 遍历待排序数组，填充计数数组。
    4. 根据计数数组，重新构建排序后的数组。
    """
    if not arr:  # 如果列表为空，直接返回
        return []
    
    # 找到数组中的最大值和最小值
    max_val, min_val = max(arr), min(arr)
    range_of_elements = max_val - min_val + 1  # 确定范围
    
    # 初始化计数数组
    count_arr = [0] * range_of_elements
    
    # 统计每个元素的出现次数
    for num in arr:
        count_arr[num - min_val] += 1
    
    # 根据计数数组，重新构建排序后的数组
    sorted_arr = []
    for i in range(range_of_elements):
        sorted_arr.extend([i + min_val] * count_arr[i])
    
    return sorted_arr

# 案例
counting_sort_example = counting_sort([64, 34, 25, 12, 22, 11, 90])

计数排序是一种线性时间复杂度的排序算法，适用于元素范围较小的场景。由于它的工作原理不是基于元素之间的比较，因此它的时间复杂度可以达到 O(n)。但是，这个算法也有一定的局限性，例如，当元素范围较大或数据分布不均匀时，可能不如基于比较的排序算法高效。

第十部分：桶排序

桶排序是计数排序的一种扩展和改良，也是一种线性时间复杂度的排序算法。它将待排序的元素分配到有限数量的桶中，每个桶中的元素再分别进行排序。通常利用插入排序来对桶中的元素进行排序。

算法描述
1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。
代码解读与案例

def bucket_sort(arr):
    """
    桶排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 找出待排序数组中的最大值和最小值，确定范围。
    2. 初始化若干个桶，每个桶存储一定范围内的元素。
    3. 遍历待排序数组，将每个元素放入对应的桶中。
    4. 对每个非空桶内的元素进行排序，通常使用插入排序。
    5. 将所有非空桶中的元素按桶的顺序合并成最终的排序数组。
    """
    if not arr:  # 如果列表为空，直接返回
        return []
    
    # 找到数组中的最大值和最小值
    max_val, min_val = max(arr), min(arr)
    bucket_range = (max_val - min_val) / len(arr)  # 每个桶的数值范围
    count = int((max_val - min_val) // bucket_range) + 1  # 桶的数量
    
    # 初始化桶
    buckets = [[] for _ in range(count)]
    
    # 将每个元素放入对应的桶中
    for num in arr:
        idx = int((num - min_val) // bucket_range)
        buckets[idx].append(num)
    
    # 对每个非空桶内的元素进行排序
    for i in range(count):
        buckets[i] = sorted(buckets[i])
    
    # 将所有非空桶中的元素按桶的顺序合并成最终的排序数组
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)
    
    return sorted_arr

# 案例
bucket_sort_example = bucket_sort([64, 34, 25, 12, 22, 11, 90])

桶排序是一种非常有效的排序算法，特别适用于数据分布均匀，数据范围较小的场景。其时间复杂度为 O(n+k)，其中 n 是待排序数组的长度，k 是桶的数量。在实际应用中，通过适当选择桶的数量和大小，可以实现非常高效的排序。

第十一部分：基数排序

基数排序是一种非比较整数排序算法，它是一种线性时间复杂度的稳定排序算法。它的工作原理是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成了一个有序序列。

算法描述
1. 取得数组中的最大数，并取得位数；
2. 对数组按照“个位”进行排序；
3. 对数组按照“十位”进行排序；
4. 依此类推，对数组按照最高位进行排序。
代码解读与案例

def radix_sort(arr):
    """
    基数排序
    
    :param arr: 待排序的列表
    :return: 排序后的列表
    
    算法步骤：
    1. 找出列表中的最大值，确定最大值的位数，即最大的排序位数。
    2. 从个位数开始，根据位数的值将元素分配到0-9号桶中。
    3. 按照桶的顺序，将元素重新组合成列表。
    4. 进行下一位的排序，重复步骤2-3，直到最高位。
    """
    if not arr:  # 如果列表为空，直接返回
        return []
    
    # 找出列表中的最大值，确定最大的排序位数
    max_num = max(arr)
    max_length = len(str(max_num))
    
    # 从个位数开始，进行每一位的排序
    for i in range(max_length):
        # 初始化桶
        buckets = [[] for _ in range(10)]
        
        # 将每个元素根据当前位的数字放到0-9号桶中
        for num in arr:
            digit = (num // (10 ** i)) % 10  # 获取当前位的数字
            buckets[digit].append(num)
        
        # 按照桶的顺序，将元素重新组合成列表
        arr = [num for bucket in buckets for num in bucket]
    
    return arr

# 案例
radix_sort_example = radix_sort([170, 45, 75, 90, 802, 24, 2, 66])

基数排序是一种非常高效的排序算法，其时间复杂度为 O(nk)，其中 n 是列表长度，k 是数字的最大长度。但是基数排序仅适用于正整数，且要求数据的分布较为均匀。在满足这些前提条件的情况下，基数排序是一种非常实用和高效的排序方法。

总结

在本篇博客中，我们详细探讨了各种排序算法的原理和实现。每个排序算法都有其适用场景和优劣，理解它们的工作原理和特性有助于我们更加合理和高效地解决实际问题。

算法比较
**冒泡排序、选择排序和插入排序 **是最基础的排序算法，容易理解和实现，但是它们的时间复杂度较高，适合小规模数据的排序。
**归并排序和快速排序 **都采用了分治的策略，能够在较大数据集上表现良好，快速排序在实际应用中被认为是最快的通用排序算法。
**堆排序 **利用了堆这一数据结构，是一种原地排序算法，其时间复杂度稳定在 (nlogn)。
计数排序、桶排序和基数排序 是非基于比较的线性时间复杂度排序算法，适用于特定类型的输入数据。
选择建议
在实际应用中，选择排序算法时需要综合考虑数据的规模、特性以及算法的时间和空间复杂度：
1. **小规模数据：**可以选择简单的算法，如冒泡排序、插入排序或选择排序。
2. **大规模且数据随机分布：**可以选择快速排序。
3. **大规模且需要稳定排序：**可以选择归并排序。
4. **元素范围有限且分布均匀：**可以选择非比较的线性时间复杂度算法，如计数排序、桶排序或基数排序。
结语
排序算法是算法学习和研究的基础内容，掌握常见的排序算法有助于提升我们的算法设计和编程能力。希望本篇博客能够帮助大家更好地理解和学习排序算法。