在列表中添加插入排序的成本

Question

我正在尝试添加插入排序的每个部分的成本（下图中用蓝色标记）
目前我写的代码是这样的：

\begin{lstlisting}[escapeinside=`']
    InsertionSort(A)
        n = A.length
        for j=2 to n
        `\begin{equation*}
            n-1
                \begin{cases}
                    key = A[j] \\
                    i = j-1;\\
                    while(i>0) and (A[i] > key)\\
                        A[i+1] = A[i]\\
                        i = i-1 \\
                    A[i+1] = key;
                \end{cases}
        \end{equation*}'
\end{lstlisting}

我知道这个代码片段无法正常工作。我希望有人能帮助我

编辑：可能lstlisting不是合适的使用环境。
我对 LaTeX 还很陌生，所以每一条建议我都接受

編輯2：我也尝试过clrscode3e，但我不知道如何继续

\documentclass{article}

\usepackage{clrscode3e}

\begin{document}

\begin{codebox}
\Procname{$\proc{InsertionSort}(A)$}
\li $n \gets \attrib{A}{length}$
\li     \For $j \gets 2$ \To $n$
\li     \Do
            $\id{key} \gets A[j]$
\li         $i \gets j-1$
\li         \While $(i > 0)$ and $A[i] > \id{key}$
\li             \Do
                    $A[i + 1] = A[i]$
\li                 $i \gets i-1$
                \End
\li         $A[i+1] \gets \id{key}$
        \End
\end{codebox}

\end{document}

Answer 1

由于您想使用跨多行的括号，tikzmark因此可以使用 s。我不得不承认，代码看起来有点过载，但我没有找到在每行开头插入代码的其他可能性。

\documentclass{article}

\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{tikzmark}
\usetikzlibrary{decorations.pathreplacing}

\begin{document}

\begin{lstlisting}[%
    escapeinside=`', 
    basicstyle=\linespread{1.2}\selectfont,
    morekeywords={InsertionSort},
    keywordstyle=\underbar
]
`\tikzmark{l1}'InsertionSort(A)
`\tikzmark{l2}'n = A.length 
`\tikzmark{l3}'    for j=2 to n
`\tikzmark{l4}'    key = A[j] 
`\tikzmark{l5}'        i = j-1
`\tikzmark{l6}'        while(i>0) and (A[i] > key)
`\tikzmark{l7}'            A[i+1] = A[i]
`\tikzmark{l8}'            i = i-1 
`\tikzmark{l9}'        A[i+1] = key;
\end{lstlisting}

\begin{tikzpicture}[remember picture, overlay,
    span/.style={cyan, decorate, decoration={brace, mirror}},
    cost/.style={cyan, anchor=base, align=left, text width=75pt},
]
    \draw[span] ([xshift=3em, yshift=.9em]pic cs:l5) -- ([xshift=3em]pic cs:l9) node[pos=.5,left] {$n-1$};
    \draw[span] ([xshift=5.5em, yshift=.9em]pic cs:l7) -- ([xshift=5.5em]pic cs:l8) node[pos=.5,left] {$t_j$};
    
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l1) (n1) {$C_0$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l2) (n2) {$C_1$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l3) (n3) {$C_2 \cdot n$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l4) (n4) {$C_3 \cdot (n - 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l5) (n5) {$C_4 \cdot (n - 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l6) (n6) {$C_5 \cdot \sum^n_{j=2} (t_j + 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l7) (n7) {$C_6 \cdot \sum^n_{j=2} t_j$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l8) (n8) {$C_7 \cdot \sum^n_{j=2} t_j$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:l9) (n9) {$C_8 \cdot (n - 1)$};
\end{tikzpicture}

\end{document}

---

编辑：我刚刚发现该tikzmark软件包已经附带了一些对该listings软件包的支持。因此，上述内容也可以按如下方式实现。然后甚至可以轻松地在每行代码的末尾包含一些将节点连接到右侧的行。

\documentclass{article}

\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{tikzmark}
\usetikzmarklibrary{listings}
\usetikzlibrary{decorations.pathreplacing}

\begin{document}

\begin{lstlisting}[
    basicstyle=\linespread{1.2}\selectfont,
    morekeywords={InsertionSort},
    keywordstyle=\underbar,
    name=code,
]
InsertionSort(A)
n = A.length 
    for j=2 to n
    key = A[j] 
        i = j-1
        while(i>0) and (A[i] > key)
            A[i+1] = A[i]
            i = i-1 
        A[i+1] = key;
\end{lstlisting}

\begin{tikzpicture}[remember picture, overlay,
    span/.style={cyan, decorate, decoration={brace, mirror}},
    cost/.style={cyan, anchor=base, align=left, text width=75pt},
]
    \draw[span] ([xshift=3em, yshift=.9em]pic cs:line-code-5-start) -- ([xshift=3em]pic cs:line-code-9-start) node[pos=.5,left] {$n-1$};
    \draw[span] ([xshift=5.5em, yshift=.9em]pic cs:line-code-7-start) -- ([xshift=5.5em]pic cs:line-code-8-start) node[pos=.5,left] {$t_j$};
    
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-1-start) (n1) {$C_0$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-2-start) (n2) {$C_1$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-3-start) (n3) {$C_2 \cdot n$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-4-start) (n4) {$C_3 \cdot (n - 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-5-start) (n5) {$C_4 \cdot (n - 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-6-start) (n6) {$C_5 \cdot \sum^n_{j=2} (t_j + 1)$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-7-start) (n7) {$C_6 \cdot \sum^n_{j=2} t_j$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-8-start) (n8) {$C_7 \cdot \sum^n_{j=2} t_j$};
    \node[cost] at ([xshift={\textwidth-75pt}]pic cs:line-code-9-start) (n9) {$C_8 \cdot (n - 1)$};
    
    \foreach \i in {1,...,9} 
        \draw[dashed, cyan] ([xshift=5pt]pic cs:line-code-\i-end) -- (n\i.base west);
    
\end{tikzpicture}

\end{document}