63 lines
3.2 KiB
TeX
63 lines
3.2 KiB
TeX
|
\documentclass[实验报告模板]{subfiles}
|
||
|
|
|
||
|
|
\renewcommand{\mydate}{
|
||
|
|
2023/12/29
|
||
|
|
}
|
||
|
|
\renewcommand{\mychapternum}{8}
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
\mytitle
|
||
|
|
\begin{enumerate}
|
||
|
|
\myitem{实验目的}{
|
||
|
|
\item 使用第八章的知识解决排序的综合
|
||
|
|
问题。
|
||
|
|
}
|
||
|
|
\myitem{实验内容}{
|
||
|
|
\item 给定一个序列，使用快速排序将其从小到大进行排列。
|
||
|
|
\item 给定一个序列，构造一个大根堆。
|
||
|
|
}
|
||
|
|
\myitem{实验原理}{
|
||
|
|
\item 程序设计原理。
|
||
|
|
}
|
||
|
|
\myitem{实验步骤}{
|
||
|
|
\item 问题抽象
|
||
|
|
\item 编写程序
|
||
|
|
\item 调试程序
|
||
|
|
\item 完善总结
|
||
|
|
}
|
||
|
|
\myitem{调试过程、结果和分析}{
|
||
|
|
\item 两道题分别对应了快速排序和堆排序。
|
||
|
|
\item 快速排序要注意好起点和终点的位置选取，作为比较标准的元素放在最前面，开始位置为数组的开始，开始元素为这个元素后面的一个元素，结束元素为数组末尾的元素。需要维护两个指针，分别从开始往后移动和从末尾往前移动，用来标记下一个要交换的位置。最后这两个指针交汇时的位置就是比较标准的元素需要放置的位置了。
|
||
|
|
\item 堆排序要注意不同的操作，构造堆时从最后一个非叶子节点开始往前逐个下沉，当然也可以看做向一个空的堆中不断插入来完成构造；插入操作是先插入到末尾然后上浮；弹出操作是将堆顶的元素弹出，之后把末尾的元素放到对顶再下沉。
|
||
|
|
\item 下沉操作比上浮操作更复杂一点，因为要比较父节点和左右两个子节点，把最大的子节点换上了，而上浮操作只需要和父节点比较就行。
|
||
|
|
\item 快速排序的
|
||
|
|
输入：\\
|
||
|
|
20\\
|
||
|
|
41 40 19 8 5 5 17 32 39 32 98 95 68 56 60 59 67 94 77 98
|
||
|
|
|
||
|
|
输出：\\
|
||
|
|
5 5 8 17 19 32 32 39 40 41 56 59 60 67 68 77 94 95 98 98
|
||
|
|
|
||
|
|
\item 大根堆的
|
||
|
|
输入：\\
|
||
|
|
20\\
|
||
|
|
41 40 19 8 5 5 17 32 39 32 98 95 68 56 60 59 67 94 77 98
|
||
|
|
|
||
|
|
输出：\\
|
||
|
|
逐个插入后，逐个弹出输出的结果为：\\
|
||
|
|
98 98 95 94 77 68 67 60 59 56 41 40 39 32 32 19 17 8 5 5\\
|
||
|
|
一次性初始化后，逐个弹出输出的结果为：\\
|
||
|
|
98 98 95 94 77 68 67 60 59 56 41 40 39 32 32 19 17 8 5 5
|
||
|
|
}
|
||
|
|
\myitem{总结}{
|
||
|
|
\item 在大根堆排序时，如果不使用弹出，而是每次把堆顶的元素和堆末尾的元素交换，之后将堆的长度减一，这样操作完成后就会形成升序排列。如果每次把堆顶的元素弹出，并且输出，这样操作完成后就会形成降序排列。这里使用的是弹出方式。
|
||
|
|
}
|
||
|
|
\myitem{附件}{
|
||
|
|
\itemsep 5em
|
||
|
|
\item 第八章作业1.cpp
|
||
|
|
\inputminted[]{cpp}{../C++/第八章作业/第八章作业1.cpp}
|
||
|
|
\item 第八章作业2.cpp
|
||
|
|
\inputminted[]{cpp}{../C++/第八章作业/第八章作业2.cpp}
|
||
|
|
}
|
||
|
|
\end{enumerate}
|
||
|
|
\end{document}
|