1. 题目一

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

希尔排序算法又称最小增量排序算法，其基本思想：

• 步骤1：构造一个步长序列 $\text{delta}_1$、$\text{delta}_2 \dots \text{delta}_k$，其中 $\text{delta}_1 = n/2$，后面的每个 $\text{delta}$ 是前一个的 $1/2$，$\text{delta}_k = 1$。
• 步骤2：根据步长序列、进行 $k$ 趟排序。
• 步骤3：对第 $i$ 趟排序，根据对应的步长 $\text{delta}$，将等步长位置元素分组，对同一组内元素在原位置上进行直接插入排序。

1. 考点：解题技巧

• 常见技巧：1、仔细看 2、编程经验 3、给变量代入数据，尝试在脑海中运行程序

1.1 解题技巧：仔细检查所有用到的变量。

1.1.1 题目

......
int main() {
    int i,j,count=1;
    int pos[N+1];
    for(i=1; i<=N; i++) { //初始化位置
        pos[i]=0;
    }
    (1) ;  //此处缺少j的初始赋值
    while(j>=1) {
        pos[j]=pos[j]+1;
            while(pos[j]<=N&& __) {/*尝试摆放第i个皇后*/
            pos[j]=pos[j]+1;
        }
    }
}

1. 知识点分布

2. 学习内容摘要

2.1 理论基础

2.1.1 时间复杂与空间复杂度

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。

常见的对算法执行所需时间的度量：$O(1) < O(\log_2 n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n)$

这里记录家庭网络、街霸游戏以及其他日常实践与兴趣内容。

学习目录

• 家庭网络
• 街霸
• 杂项

这里记录家庭组网、网络设备与日常网络实践。

这里记录浏览器、工具与其他零散但实用的内容。

这里记录《街霸 6》的基础概念、角色资料与实战经验。

1. 考点：分治法

1.1 知识点概览

算法策略 —— 考点：算法策略概述（分治法）

• 特征：把一个问题拆分成多个小规模的相同子问题，一般用递归解决，也可以用循环。
• 经典问题：归并排序、快速排序、矩阵乘法、二分搜索、斐波那契数列、大整数乘法、汉诺塔。
• 关键词：一分为二、一一合二。
• 注意：不要陷入到递归调用的证明，直接调用下层即可。

1. 考点：常见排序算法的对比

1.1 常见排序算法性能对比总览

1. 考点：基础概况

1.1 知识点概览

排序算法 —— 其他类排序：基数排序（Radix Sort）

• 基本思想：

  • 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。
  • 它不是基于关键字比较的排序方法，因此非常适合于元素数量很多但关键字较少的序列。
  • 基数选择和关键字的分解取决于关键字的类型，例如十进制数可按个位、十位进行分解。