如何在Julia中为Insertion和Merge排序图表标注交点？

核心目标 #

找到**插入排序（Insertion sort）与归并排序（Merge sort）**性能曲线的交点（即两种算法运行时间相等的输入规模点），并在图表上标注该点的坐标与对应信息。

分步实现 #

1. 准备排序算法与性能测试代码 #

首先实现两种排序算法，并编写函数测试不同输入规模下的运行时间：

using BenchmarkTools, Plots

# 插入排序
function insertion_sort!(arr)
    for i in 2:length(arr)
        key = arr[i]
        j = i - 1
        while j > 0 && arr[j] > key
            arr[j+1] = arr[j]
            j -= 1
        end
        arr[j+1] = key
    end
    return arr
end

# 归并排序
function merge_sort(arr)
    length(arr) ≤ 1 && return arr
    mid = length(arr) ÷ 2
    left = merge_sort(arr[1:mid])
    right = merge_sort(arr[mid+1:end])
    return merge(left, right)
end

function merge(left, right)
    result = similar(left, length(left) + length(right))
    i = j = 1
    for k in eachindex(result)
        if i > length(left)
            result[k] = right[j]
            j += 1
        elseif j > length(right)
            result[k] = left[i]
            i += 1
        elseif left[i] ≤ right[j]
            result[k] = left[i]
            i += 1
        else
            result[k] = right[j]
            j += 1
        end
    end
    return result
end

# 批量测试不同规模的运行时间
function benchmark_sorts(sizes)
    insertion_times = Float64[]
    merge_times = Float64[]
    for n in sizes
        arr = rand(n)
        # 取最小运行时间保证精度，转换为秒
        t_insert = minimum(@benchmark insertion_sort!($copy(arr)).times) / 1e9
        t_merge = minimum(@benchmark merge_sort($arr)).times / 1e9
        push!(insertion_times, t_insert)
        push!(merge_times, t_merge)
    end
    return sizes, insertion_times, merge_times
end

2. 计算曲线交点 #

通过对比相邻输入规模的时间数据，找到算法性能反转的区间，再用线性插值估算精确交点：

function find_intersection(sizes, t_insert, t_merge)
    for i in 2:length(sizes)
        # 找到插入排序从快于归并排序转为慢于的区间
        if t_insert[i-1] < t_merge[i-1] && t_insert[i] > t_merge[i]
            n1, n2 = sizes[i-1], sizes[i]
            t1_ins, t2_ins = t_insert[i-1], t_insert[i]
            t1_mer, t2_mer = t_merge[i-1], t_merge[i]
            
            # 线性插值求解交点的输入规模n
            numerator = (t1_mer - t1_ins) * (n2 - n1)
            denominator = (t2_ins - t1_ins) - (t2_mer - t1_mer)
            n_intersect = n1 + numerator / denominator
            
            # 计算交点对应的运行时间
            t_intersect = t1_ins + (t2_ins - t1_ins)/(n2 - n1) * (n_intersect - n1)
            return n_intersect, t_intersect
        end
    end
    return nothing  # 未找到交点时返回，可扩大测试规模重试
end

3. 绘制图表并标注交点 #

用Plots库生成性能曲线，添加交点的散点与文字标注：

# 定义测试的输入规模范围
sizes = 10:10:1000
n_vals, t_insert, t_merge = benchmark_sorts(sizes)

# 获取交点数据
intersection = find_intersection(n_vals, t_insert, t_merge)

# 绘制基础曲线
plt = plot(n_vals, t_insert, label="插入排序", 
           xlabel="输入规模n", ylabel="运行时间（秒）", 
           title="排序算法性能对比")
plot!(plt, n_vals, t_merge, label="归并排序")

# 标注交点（如果找到）
if intersection !== nothing
    n_inter, t_inter = intersection
    scatter!(plt, [n_inter], [t_inter], color=:red, label="交点")
    annotate!(plt, n_inter + 50, t_inter, 
              text("n≈$(round(Int, n_inter))\nt≈$(round(t_inter, digits=4))s", :left, 8))
end

display(plt)

新手操作提示 #

• 先安装依赖包：执行using Pkg; Pkg.add(["BenchmarkTools", "Plots"])
• 若未找到交点，可扩大sizes的范围（比如改成10:10:2000）
• 可分步运行代码：先验证排序函数正确性，再测试时间，最后处理交点与绘图

内容的提问来源于stack exchange，提问作者wrisurcuriosity