Press Ctrl+ and K to search
常见排序算法原理
- 冒泡排序（
Bubble Sort）原理：重复地遍历待排序的序列，每次比较相邻元素，如果顺序错误则交换，直至序列完全有序。 - 插入排序（
Insertion Sort）原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 - 选择排序（
Selection Sort）原理：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后继续从剩余未排序元素中选择最小（大）元素，放到已排序序列的末尾。 - 归并排序（
Merge Sort）原理：采用分治法，将序列分成若干子序列，每个子序列排好序后，再将子序列合并成一个整体。 - 快速排序（
Quick Sort）原理：采用分治法，通过选择一个基准元素将序列分成两部分，一部分小于基准元素，一部分大于基准元素，递归排序两部分。 - 堆排序（
Heap Sort）原理：利用堆这种数据结构来排序，首先构建最大堆，然后将堆顶元素与末尾元素交换，再对剩余元素重新调整为最大堆，重复进行。 - 希尔排序（
Shell Sort）原理：基于插入排序，通过不断缩小的增量对序列进行排序，最后一次使用插入排序。 - 计数排序（
Counting Sort）原理：适用于范围有限的整数序列，统计每个元素出现的次数，然后依次输出。 - 桶排序（
Bucket Sort）原理：将元素分布到不同的桶中，每个桶内单独排序（通常使用插入排序或其他适合的排序算法），最后合并桶。 - 基数排序（
Radix Sort）原理：按位（个位、十位、百位等）排序，从低位到高位进行，适用于整数或字符串排序。
常见排序算法对比
| 排序算法 | 最好情况时间复杂度 | 最坏情况时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | 稳定 | |||
| 选择排序 | 否 | |||
| 插入排序 | 稳定 | |||
| 希尔排序 | 否 | |||
| 归并排序 | 稳定 | |||
| 快速排序 | 否 | |||
| 堆排序 | 否 | |||
| 计数排序 | 稳定 | |||
| 桶排序 | 稳定 | |||
| 基数排序 | 稳定 |
简介
本文用于记录软考中，编程语言相关的考试题目，这些题目一般包含编程语言的语法、原理等，仅与对应的编程语言有关的题目。
在软考中，与编程语言有关的题目，主要涉及以下编程语言：
- C
- C++
- Python
- Java
其中Python在上半场理论选择题考试中较为常见，几乎每次都有2分以上的题目。
C语言设计的题目基本上集中在下半场实践考试的第四题，算法题目中。
Java和C++一般出现在最后一题，Java和C++各一题，选作其中之一即可。
如有想要记录的题目，欢迎评论补充！
简介
本文记录一些软考中关于法律的知识点。
如有想要记录的题目，欢迎评论补充！
关注公众号“月上老狗”，发送“软件设计师”，获取历年软件设计师软考真题。
简介
UML图是一种统一建模语言（Unified Modeling Language）的图形表示，用于描述软件系统的结构和行为。它是一种标准化的图形化语言，被广泛应用于软件开发领域，用于可视化、规划和构建软件系统。UML图提供了一种可视化的方法来描述系统的各个方面，包括静态结构、动态行为、交互和用例等。常见的UML图包括类图、用例图、时序图、活动图、状态图等。
下面是几个常见的分类：
- 类图（
Class Diagram）：描述系统中的类、属性和方法之间的关系，是静态结构的表示。 - 用例图（
Use Case Diagram）：描述系统中的功能需求和用户之间的交互，以及系统对外部实体的行为。 - 时序图（
Sequence Diagram）：描述系统中对象之间的交互顺序，特别适用于描述系统的动态行为。 - 活动图（
Activity Diagram）：描述系统中的活动流程和控制流程，用于展示系统中的业务流程或算法流程。 - 状态图（
State Diagram）：描述系统中对象的状态以及状态之间的转换，用于表示对象在不同状态下的行为变化。
关注公众号“月上老狗”，发送“软件设计师”，获取历年软件设计师软考真题。
常见考点
- 活动图的关键路径：活动图的关键路径是指开始到结束，距离（耗时）最长的路径。
提示：本地新建 html 文件，拷贝代码填入文件后，浏览器查看即可查看效果。
html<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Collapsible Tree with D3.js</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
/* 定义节点样式 */
.node {
cursor: pointer;
}
.node circle {
fill: #fff;
stroke: steelblue;
stroke-width: 3px;
}
.node text {
font: 12px sans-serif;
}
.link {
fill: none;
stroke: #ccc;
stroke-width: 2px;
}
</style>
</head>
<body>
<script>
// 定义树数据结构
var treeData = {
name: "Root",
children: [
{
name: "Child 1",
children: [
{ name: "Grandchild 1.1" },
{ name: "Grandchild 1.2" }
]
},
{ name: "Child 2" }
]
};
// 定义树图的边距和尺寸
var margin = { top: 20, right: 120, bottom: 20, left: 120 },
width = 960 - margin.right - margin.left,
height = 500 - margin.top - margin.bottom;
var i = 0,
duration = 750, // 动画持续时间
root;
// 创建树布局
var tree = d3.tree().size([height, width]);
// 创建对角线生成器
var diagonal = d3.linkHorizontal().x(d => d.y).y(d => d.x);
// 创建SVG容器
var svg = d3.select("body").append("svg")
.attr("width", width + margin.right + margin.left)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
// 将数据转换为树节点
root = d3.hierarchy(treeData, d => d.children);
root.x0 = height / 2;
root.y0 = 0;
// 初始折叠函数，递归折叠所有子节点
function collapse(d) {
if (d.children) {
d._children = d.children; // 将子节点保存到隐藏节点中
d._children.forEach(collapse);
d.children = null; // 清空子节点，实现折叠
}
}
// 初始化时折叠所有子节点
root.children.forEach(collapse);
update(root); // 更新树图
function update(source) {
// 将数据映射为树布局
var treeData = tree(root);
// 获取所有节点和链接
var nodes = treeData.descendants(),
links = treeData.links();
// 标准化节点深度
nodes.forEach(d => { d.y = d.depth * 180 });
// ****************** 节点部分 ******************
// 使用唯一ID绑定数据
var node = svg.selectAll('g.node')
.data(nodes, d => d.id || (d.id = ++i));
// 为新节点添加g元素
var nodeEnter = node.enter().append('g')
.attr('class', 'node')
.attr('transform', d => 'translate(' + source.y0 + ',' + source.x0 + ')')
.on('click', click); // 绑定点击事件
// 添加圆形元素表示节点
nodeEnter.append('circle')
.attr('r', 1e-6)
.style('fill', d => d._children ? "lightsteelblue" : "#fff");
// 添加文本标签
nodeEnter.append('text')
.attr('dy', '.35em')
.attr('x', d => d.children || d._children ? -13 : 13)
.attr('text-anchor', d => d.children || d._children ? "end" : "start")
.text(d => d.data.name);
// 过渡更新节点
var nodeUpdate = nodeEnter.merge(node);
// 将节点过渡到新位置
nodeUpdate.transition()
.duration(duration)
.attr('transform', d => 'translate(' + d.y + ',' + d.x + ')');
// 更新节点样式
nodeUpdate.select('circle')
.attr('r', 10)
.style('fill', d => d._children ? "lightsteelblue" : "#fff");
// 过渡移除旧节点
var nodeExit = node.exit().transition()
.duration(duration)
.attr('transform', d => 'translate(' + source.y + ',' + source.x + ')')
.remove();
// 在退出时缩小节点
nodeExit.select('circle')
.attr('r', 1e-6);
nodeExit.select('text')
.style('fill-opacity', 1e-6);
// ****************** 链接部分 ******************
// 使用唯一ID绑定数据
var link = svg.selectAll('path.link')
.data(links, d => d.target.id);
// 为新链接添加path元素
var linkEnter = link.enter().insert('path', 'g')
.attr('class', 'link')
.attr('d', d => {
var o = { x: source.x0, y: source.y0 };
return diagonal({ source: o, target: o });
});
// 过渡更新链接
var linkUpdate = linkEnter.merge(link);
// 将链接过渡到新位置
linkUpdate.transition()
.duration(duration)
.attr('d', diagonal);
// 过渡移除旧链接
var linkExit = link.exit().transition()
.duration(duration)
.attr('d', d => {
var o = { x: source.x, y: source.y };
return diagonal({ source: o, target: o });
})
.remove();
// 将旧位置存储以便过渡
nodes.forEach(d => {
d.x0 = d.x;
d.y0 = d.y;
});
// 点击事件处理函数
function click(event, d) {
if (d.children) {
d._children = d.children;
d.children = null; // 折叠子节点
} else {
d.children = d._children;
d._children = null; // 展开子节点
}
update(d); // 更新树图
}
}
</script>
</body>
</html>
