[总结/备赛]备战 CSP-S 2025 初赛总结

被拉到dl24jp集训一整天(我的作业啊啊啊啊啊)

1.排序算法

主要考察稳定性，时间复杂度，原理

1.1.插入排序

最佳时间复杂度：\(O(n)\)

最差时间复杂度：\(O(n^2)\)

平均时间复杂度：\(O(n^2)\)

是否稳定：是

1.2.希尔排序(优化插入排序)

就是把元素分组，每组gap个，对gap中的元素进行插入排序。不断缩小gap值，直至gap=1,进行最后一次排序，之后得到的序列就是有序的

说白了每次进行完插入排序会使大的元素集中在一侧，这样就可以使插入排序之后的比较次数少

最佳时间复杂度：\(O(n log n)\)

最差时间复杂度：\(O(n^2)\)

平均时间复杂度：\(O(n log^2 n)\)

是否稳定：否

补：关于时间复杂度的说明

根据gap每次的取值不同，预排序的效果也不同，最后一次插入排序的效率也就不同

1.3.选择排序

设第\(n\)个元素为基准，向后遍历找最小值，然后和第\(n+1\)个元素交换

这样每次放的都是第\(n+1\)小的元素

最佳时间复杂度:\(O(n^2)\)

最差时间复杂度:\(O(n^2)\)

平均时间复杂度:\(O(n^2)\)

稳定性：否

1.4.