一、今日任务完成情况
算法新题：4 道
-
直接插入排序
-
希尔排序
-
冒泡排序
-
快速排序
SQL 新题：3 道
-
计算用户的平均次日留存率
-
计算每天用户的次日留存率
-
每个月 Top3 的周杰伦歌曲
二、今日收获 & 明日计划
今日收获
-
掌握 4 种经典排序算法的核心逻辑、适用场景和复杂度分析，能区分稳定 / 不稳定排序；
-
吃透留存率计算的核心逻辑，理解左连接和 DISTINCT 在结果准确性中的作用；
-
掌握 SQL TopN 问题的通用解法，明确窗口函数的使用规则和 SQL 执行顺序；
-
能识别 SQL 逻辑漏洞（如分母错误、日期缺失）并给出针对性改进方案。
三、解题思路
1. 算法题目
1.1 直接插入排序
题目说明：实现直接插入排序，核心逻辑为遍历数组时，将当前元素与前面已排序的元素逐一比较，找到对应位置插入，使已排序区间始终保持有序。
解题思路：
-
复制原数组避免修改原始数据，获取数组长度；
-
遍历数组每个元素，暂存当前待插入元素；
-
向前遍历已排序区间，若已排序元素大于当前元素，则将该元素向后移动；
-
找到合适位置（j+1）后插入当前元素，完成一次插入操作；
-
遍历完成后返回排序后的数组。
def insert_sort(arr):
arr_sorted = arr.copy()
n = len(arr_sorted)
for i in range(n):
current = arr_sorted[i]
j = i-1
while j >= 0 and arr_sorted[j] > current:
arr_sorted[j+1] = arr_sorted[j]
j -= 1
arr_sorted[j+1] = current
return arr_sorted
1.2 希尔排序
题目说明：实现希尔排序（插入排序改进版），核心逻辑为按指定步长将数组拆分为多个子表，对每个子表执行直接插入排序，逐步缩小步长直至为 0，最终完成整体排序。
解题思路：
-
复制原数组，获取数组长度，初始化步长为数组长度的一半；
-
当步长大于 0 时，按步长遍历数组元素，对每个元素执行子表内的插入排序；
-
子表插入排序逻辑与直接插入排序一致，仅比较和移动的步长为当前设定步长；
-
每轮排序完成后将步长折半，重复排序直至步长为 0；
-
返回排序后的数组。
def shell_sort(arr):
arr_sorted = arr.copy()
n = len(arr_sorted)
step = n // 2
while step > 0:
for i in range(step,n):
current = arr_sorted[i]
j = i - step
while j >= 0 and arr_sorted[j] > current:
arr_sorted[j+step] = arr_sorted[j]
j -= step
arr_sorted[j+step] = current
step = step // 2
return arr_sorted
1.3 冒泡排序
题目说明：实现冒泡排序，核心逻辑为从前往后两两对比相邻元素，将较大的元素逐步 “冒泡” 到数组末尾，若某一轮无元素交换则提前终止排序。
解题思路：
-
复制原数组，获取数组长度；
-
外层循环控制排序轮数，内层循环遍历未排序区间的相邻元素；
-
若前一个元素大于后一个元素则交换两者，标记本轮发生了交换；
-
若某一轮未发生任何交换，说明数组已完全有序，提前终止循环；
-
遍历完成后返回排序后的数组。
def bubble_sort(arr):
arr_sorted = arr.copy()
n = len(arr_sorted)
for i in range(n):
swapped = False
for j in range(0,n-i-1):
if arr_sorted[j] > arr_sorted[j+1]:
arr_sorted[j],arr_sorted[j+1] = arr_sorted[j+1],arr_sorted[j]
swapped = True
if not swapped:
break
return arr_sorted
1.4 快速排序
题目说明：实现快速排序（分治思想），核心逻辑为选择基准值，将数组分为 “小于基准、等于基准、大于基准” 三部分，递归排序左右两部分后合并结果。
解题思路：
-
递归终止条件：若数组为空则返回空数组；
-
选择数组第一个元素作为基准值；
-
遍历数组，将元素分别归入 “小于基准”“等于基准”“大于基准” 三个列表；
-
递归对 “小于基准” 和 “大于基准” 的列表执行快速排序；
-
合并递归结果与 “等于基准” 的列表，返回最终有序数组。
def quick_sort(arr):
if not arr:
return []
pivot = arr[0]
left = []
equal = []
right = []
for num in arr:
if num < pivot:
left.append(num)
elif num == pivot:
equal.append(num)
else:
right.append(num)
return quick_sort(left) + equal + quick_sort(right)
2. SQL 题目
2.1 计算用户的平均次日留存率
题目说明：从用户刷题记录表（question_practice_detail）中，计算用户在某天刷题后第二天还会再来刷题的平均次日留存率。
解题思路：
-
第一步（CTE t1）：去重获取用户 - 刷题日期的唯一记录，避免同一用户同一天多次刷题导致重复计数；
-
第二步（CTE t2）：通过自连接匹配出 “用户当天刷题且次日也刷题” 的记录，筛选条件为用户 ID 相同、次日日期等于当天日期 + 1 天；
-
第三步：计算留存率，分子为有次日留存的 “用户 - 日期” 数，分母为所有 “用户 - 日期” 数，结果保留 4 位小数。
with t1 as (
select
distinct
device_id,
date
from question_practice_detail
)
,t2 as (
select
b.device_id,
b.date
from t1 a left join t1 b
on a.device_id = b.device_id
where a.date < b.date and date_add(a.date,interval 1 day) = b.date
)
select
round(count(distinct t2.device_id,t2.date)/count(distinct t1.device_id,t1.date),4) as avg_ret
from t1 left join t2 on t1.device_id = t2.device_id;
2.2 计算每天用户的次日留存率
题目说明：从用户登录表（user_login）中，计算每一天登录用户的次日留存率（次日仍登录的用户数 / 当日登录总用户数），要求保留所有日期（无留存的日期留存率为 0）。
解题思路：
-
第一步（CTE t1）：去重获取用户 - 登录日期的唯一记录，确保每个用户每天只计数一次；
-
第二步（CTE t2）：自连接匹配出 “当日登录且次日也登录” 的用户，关联条件为用户 ID 相同、次日日期 = 当日日期 + 1 天，同时记录当日日期作为统计日期；
-
第三步：左连接 t1 和 t2，按登录日期分组，计算每组的留存率（分子为次日留存的用户数，分母为当日登录总用户数），结果保留 2 位小数，保证所有日期都被统计。
WITH t1 AS (
SELECT DISTINCT
user_id,
login_date
FROM user_login
),
t2 AS (
SELECT
a.login_date AS stat_date,
a.user_id
FROM t1 a
JOIN t1 b
ON a.user_id = b.user_id
AND b.login_date = DATE_ADD(a.login_date, INTERVAL 1 DAY)
)
SELECT
t1.login_date AS stat_date,
ROUND(
COUNT(DISTINCT t2.user_id) / COUNT(DISTINCT t1.user_id),
2
) AS ret
FROM t1
LEFT JOIN t2
ON t1.login_date = t2.stat_date
AND t1.user_id = t2.user_id
GROUP BY t1.login_date
ORDER BY t1.login_date;
错题归因：
-
错误类型：逻辑错
-
原因分析：
-
分母逻辑错误：误用 “次日留存的用户数” 替代 “当日总登录用户数” 作为留存率分母，违背 “留存率 = 留存数 / 总登录数” 的核心公式；
-
计数逻辑错误：关联后 count (last)/count (first) 结果恒为 1，无法正确计算比例；
-
结果完整性问题：未用左连接保留无留存的日期，导致留存率为 0 的日期被遗漏。
-
-
改进方案：
-
明确分母为 “当日所有登录用户数”，分子为 “次日仍登录的用户数”；
-
使用左连接关联统计日期和留存记录，保证所有日期都被统计；
-
用 COUNT (DISTINCT t2.user_id)/COUNT (DISTINCT t1.user_id) 精准计算留存比例。
-
-
核心考点：留存率的核心计算逻辑；左连接在日期完整性中的作用；DISTINCT 去重避免重复计数用户。
2.3 每个月 Top3 的周杰伦歌曲
题目说明：从听歌流水表（play_log）、歌曲信息表（song_info）、用户信息表（user_info）中，筛选 18-25 岁用户在 2022 年每个月播放次数排名前三的周杰伦歌曲。
解题思路：
-
第一步（CTE t1）：多表联查筛选基础数据，关联用户、歌曲、听歌记录，筛选条件为 18-25 岁用户、2022 年、周杰伦的歌曲，提取月份和歌曲名；
-
第二步（CTE t2）：按月份和歌曲名分组，统计每首歌曲每月的播放次数；
-
第三步（CTE t3）：按月份分区，对播放次数降序排序，用 ROW_NUMBER () 生成排名；
-
第四步：筛选排名≤3 的记录，得到每月播放量前三的歌曲。
with
t1 as (
select
month(a.fdate) as month,
b.song_name
from
play_log a
join song_info b on a.song_id = b.song_id
join user_info c on a.user_id = c.user_id
where
c.age between 18 and 25
and year(a.fdate) = 2022
and b.singer_name = '周杰伦'
),
t2 as (
select
month,
song_name,
count(*) as play_pv
from
t1
group by
month,
song_name
),
t3 as (
select
month,
row_number() over (
partition by
month
order by
play_pv desc
) as ranking,
song_name,
play_pv
from
t2
)
select
*
from
t3
where
ranking <= 3;
错题归因：
-
错误类型：语法 / 执行顺序错
-
原因分析：
-
违反 SQL 执行顺序：将 row_number () 窗口函数直接写在 WHERE 子句中（WHERE 执行早于窗口函数）；
-
隐式类型转换：年份筛选时用单引号包裹数值（year (a.fdate) = '2022'），降低查询效率。
-
-
改进方案：
-
将窗口函数放在 CTE 中先计算排名，再在外层 WHERE 筛选 ranking <= 3；
-
年份筛选直接用数值匹配（year (a.fdate) = 2022），避免隐式转换。
-
-
核心考点：SQL 执行顺序（FROM/JOIN → WHERE → GROUP BY → HAVING → SELECT → ORDER BY）；窗口函数的合法使用位置；TopN 问题的三种排名函数选择。
四、总结
-
算法层面：插入 / 冒泡排序适合小数据量场景，快速排序适合大规模数据，希尔排序是插入排序的高效改进版，需掌握各算法的核心步骤和复杂度；
-
SQL 层面：留存率计算核心是 “当日总活跃为分母、次日留存为分子”，需用左连接保证日期完整性；TopN 问题需先通过窗口函数计算排名，再筛选结果，且要遵循 SQL 执行顺序；
-
错题改进核心：留存率计算要避免分母错误和日期缺失，窗口函数不能直接用在 WHERE 子句中。