被拉到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)\)
稳定性：否