一、直接插入排序
-
稳定性分析 （1）稳定性指的是在排序过程中，两个相等的元素在排序后的相对位置不会发生变化，直接插入排序是稳定的排序算法。 （2）在排序过程中，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。由于相等元素在插入时不会改变它们在已排序序列中的相对位置，因此直接插入排序是稳定的。
-
时间复杂度 （1）最优情况：O(n)（当输入序列已经是有序的情况下，每次插入操作都只需比较一次，无需移动元素） （2）最劣情况：O(n^2)（当输入序列是逆序的情况下，每次插入操作都需要比较 n 次，并可能需要移动 n-1 个元素） （3）平均情况：O(n^2)
-
空间复杂度：O(1) 直接插入排序是原地排序算法，不需要额外的存储空间。
-
特点 直接插入排序通过构建有序序列，逐步将每个待排序的元素插入到已排序序列的适当位置，直到所有元素都排序完毕。
-
优点 （1）实现简单直观，代码易于编写和理解 （2）对小规模数据或几乎已经有序的数据效率高 （3）稳定性好，不会改变相等元素的相对位置 （4）原地排序，不需要额外的存储空间
-
缺点 （1）对大规模数据效率低，特别是当数据完全逆序时，时间复杂度达到最坏情况的 O(n^2) （2）需要频繁移动数据元素 （3）不适用于数据规模较大且分布不均匀的情况
-
源码：
// 直接插入排序
void InsertSort(int* arr, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i, tmp = arr[end + 1];
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + 1] = arr[end];
end--;
} else {
break;
}
}
arr[end + 1] = tmp;
}
}
二、希尔排序
-
稳定性分析 （1）希尔排序是不稳定的排序算法。 （2）在排序过程中，由于分组和增量递减的特性，相同大小的元素可能会因为分组后的插入排序操作而发生相对位置的改变。
-
时间复杂度 （1）最优情况：依赖于增量序列的选择和数据分布，但一般优于 O(n^2) （2）最劣情况：可能退化到 O(n^2) （3）平均情况：通常认为在良好选择的增量序列下，介于 O(n logn) 和 O(n^1.5) 之间
-
空间复杂度：O(1) 希尔排序是原地排序算法，不需要额外的存储空间。
-
特点 希尔排序通过引入增量序列，将数组分成若干个子序列，并对每个子序列进行直接插入排序。随着增量的递减，子序列的长度逐渐增加，直到增量为 1 时，对整个数组进行一次完整的插入排序。
-
优点 （1）相对于直接插入排序，在处理大规模数据时通常具有更高的效率 （2）空间复杂度为 O(1) （3）实现相对简单
-
缺点 （1）稳定性差，可能会改变相等元素的相对位置 （2）时间复杂度的具体表现依赖于增量序列的选择
-
源码：
