c语言原地插入排序算法

原地插入排序算法是一种基于比较的排序算法，它的时间复杂度为O(n^2)，空间复杂度为O(1)。它的基本思想是将待排序的元素分为两个部分，一部分是已经排好序的，另一部分是未排序的。每次从未排序的部分中取出一个元素，插入到已排序的部分中，直到所有元素都被插入到已排序的部分中为止。

以下是C语言实现原地插入排序的示例代码：

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

在上面的代码中，arr为待排序的数组，n为数组的长度。在循环中，我们从第二个元素开始遍历数组，将当前元素存储在temp中。然后，我们将j设置为当前元素的前一个位置，并从后往前遍历已排序的部分，将大于temp的元素向后移动一个位置。最后，我们将temp插入到正确的位置中。重复这个过程，直到所有元素都被插入到已排序的部分中。