用C语言优化插入排序

插入排序在C语言中是一种简单直观的排序算法，对于小型数据集或部分有序的数据，它的性能表现尚可。优化插入排序可以从以下几个方面入手：

1. **二分查找插入位置**：对于已排序部分，而不是从头开始搜索插入位置，可以使用二分查找的方式，减少比较次数。如果数组已经部分排序，这种方法可以显著提高效率。

void insertion_sort_optimized(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

2. **避免不必要的元素复制**：在原地排序时，当找到正确的位置后，可以直接将元素放到正确位置，而不需要创建新的内存空间。这样可以减少内存操作，尤其是在处理大型数组时。

3. **稳定性**：插入排序本身就是稳定的排序算法，但在实际应用中，如果数据中存在大量重复元素，可以通过使用额外的空间存储已经排序的前半部分，这样在插入时可以跳过已经相等的元素，减少比较次数。

4. **限制递归深度**：如果使用递归版本的插入排序，可以设置一个较小的递归深度，超出这个深度就切换到其他更高效的排序方法（如快速排序），以防止栈溢出。

**相关问题--:**
1. 插入排序的基本原理是什么？
2. 插入排序在什么情况下性能最差？
3. 如何判断一个排序算法是否稳定？