C语言插入排序的实现、稳定性、时间复杂度

C语言插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是基本的插入排序实现：

void insertion_sort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* 将arr[j]大于key的元素逐个后移 */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入到正确的位置
    }
}

插入排序的主要特点是**稳定**。这是因为如果两个相等的元素a和b，a在b前面，经过插入排序后它们的相对顺序不会改变，即a仍然在b前面。

插入排序的时间复杂度情况：
- **最好情况**（已经排序的数组）：O(n)，因为每次都能直接插入到正确位置无需移动其他元素。
- **平均情况和最坏情况**：O(n^2)，当输入数组是逆序的，需要进行n次比较和交换操作。
- **最好和最坏的情况都发生在数组完全无序的情况下**，而当数组部分有序时，效率会更高，接近线性。