\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
    \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年3月10日}

\ctexset{
    section={
        format+ = \Large \raggedright,
    }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题 \arabic{aufgc}} \emph{#1}\\}
{

\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}

\section*{插入排序}

排序中一种非常显然的方法是插入排序，其主要思想为每次将一个元素
$A[j+1]$插入到已经排序好的数列
$A[1]\leqslant A[2]\leqslant\cdots\leqslant A[i]\leqslant A[i+1]\leqslant\cdots\leqslant A[j]$
中，使得$A[i]\leqslant A[j+1]\leqslant A[i+1]$，对应算法如Algorithm \ref{alg:1}.

\begin{algorithm}
    \caption{\textsc{InsertionSort}}\label{alg:1}
    \For{$j = 2$ \KwTo A.length}{
        \emph{key} $= A[j]$\\
        \tcp{Insert A[j] into the sorted sequence A[1..j-1]}
        $i = j - 1$\\
        \While{$i>0$ and $A[i]>$ \emph{key}}{
            $A[i+1] = A[i]$\\
            $i=i-1$
        }
        $A[i+1]=$\emph{key}
    }
\end{algorithm}

要证明插入排序的算法正确性，只需使用对数列按照下标依次归纳即可。

W.l.o.g.: Without loss of generality

运行时间：

- 最坏时间复杂度为
\[\sum_{j=2}^n(O(1) + \sum_i O(1))\leqslant O(n) + \sum_{j=2}^n O(j)=O(n^2)\]

\begin{definition}
    $I=$输入，$P(I)=$所有$I$的排列，则\textbf{均摊时间复杂度}为$E_{i\in P(I)}[Time(Algorithm(i))]$.
\end{definition}

- 由定义，求均摊时间复杂度，每次期望的可能性为$n/2$，可得最终的时间
复杂度仍为$O(n^2)$

- 那么应该如何改进？一种方式是希尔排序。 

\section*{希尔排序}

希尔排序的主要思想为设置步长，将$A[j+1]$插入到已排序的序列中，但比较
的对象变为$A[j-h],A[j-2h],\cdots$，算法如Algorithm\ref{insertSort}.

\begin{algorithm}
    \caption{Shell-sort}\label{insertSort}
    \SetKwFunction{insert}{InsertionSort}
    \SetKwProg{Fn}{Function}{:}{end\ Function}
    \KwIn{$H\ni 1$}
    \Fn{\insert{h}}{
        \For{$j = h+1$ \KwTo A.length}{
           \emph{key} $= A[j]$\\
           $i = j - h$\\
           \While{$i>0$ and $A[i]>$ \emph{key}}{
               $A[i+h] = A[i]$\\
               $i=i-h$
           }
           $A[i+h]=$\emph{key}
        }
    }
    \ForEach{$h\in H$(from the largest to 1)}{\insert{h}}
\end{algorithm}

注意到这一算法的最后一步\textsc{InsertionSort}中$h=1$，也就是进行
插入排序，由前述插入排序的正确性可以得到希尔排序的正确性。

那么为什么希尔排序可以降低运行时间的呢？

首先看一个例子：$H={h_2=\sqrt{n},h_1=1}$，则时间为$T(h_2)+T(h_1)$，
其中$T(h_2)$最大为$n^2/h_2$，而对$h_1=1$，期望最好的情况为每次都在
长为$h_2$的数列里进行排序，对应$O(h_2)$，因此$H$对应理想时间复杂度
为$O(n^{1.5})$.但这取决于原本数列的性质，但实际上有如下定理\ref{thm:1}.

\begin{theorem}\label{thm:1}
    $H=\{2^k-1|k=\log_2n,\cdots,1\}$，希尔排序的运行时间为$O(n^{3/2})$
\end{theorem}

证明需要用到引理\ref{lemma:1}，以$\sqrt{n}$为界，将$H$分为两部分，
小于的部分显然，大于的部分由引理可得。

\begin{lemma}\label{lemma:1}
    如果调用$h_{t+1}$和$h_t$，则调用$h_{t-1}$的时间为
    \[O(\frac{n\cdot h_{t+1}\cdot h_t}{h_{t-1}})\]
\end{lemma}

证明留作习题。

注：1.希尔排序选取足够好的$H$可以得到$O(n\log^2n)$的时间复杂度

2.希尔排序不是理论上最快的排序方法，但可以节省空间，其空间复杂度为
$O(1)$.

\section*{归并排序}

两个排序好的序列$A[p],\cdots,A[j-1]$和$A[j],\cdots,A[k]$，合并的时
间为$O(k-p)$.

\end{document}
