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插入到正确的位置中。重复这个过程，直到所有元素都被插入到已排序的部分中。

相关问题

使用原地归并排序算法和在小规模数据时采用插入排序算法的归并排序算法的C语言实现代码

以下是原地归并排序算法和在小规模数据时采用插入排序算法的归并排序算法的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MIN_SIZE 10

void merge(int *arr, int *tempArr, int leftPos, int rightPos, int rightEnd)
{
    int leftEnd = rightPos - 1;
    int tempPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    while (leftPos <= leftEnd && rightPos <= rightEnd)
    {
        if (arr[leftPos] <= arr[rightPos])
            tempArr[tempPos++] = arr[leftPos++];
        else
            tempArr[tempPos++] = arr[rightPos++];
    }

    while (leftPos <= leftEnd)
        tempArr[tempPos++] = arr[leftPos++];

    while (rightPos <= rightEnd)
        tempArr[tempPos++] = arr[rightPos++];

    for (int i = 0; i < numElements; ++i, --rightEnd)
        arr[rightEnd] = tempArr[rightEnd];
}

void mSort(int *arr, int *tempArr, int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;

        mSort(arr, tempArr, left, center);
        mSort(arr, tempArr, center + 1, right);

        if (arr[center] > arr[center + 1])
            merge(arr, tempArr, left, center + 1, right);
    }
}

void mergeSort(int *arr, int n)
{
    int *tempArr = malloc(n * sizeof(int));
    if (tempArr != NULL)
    {
        mSort(arr, tempArr, 0, n - 1);
        free(tempArr);
    }
    else
    {
        printf("Error: Out of memory\n");
        exit(1);
    }
}

void insertionSort(int *arr, int n)
{
    for (int i = 1; i < n; ++i)
    {
        int j = i;
        int tmp = arr[i];

        while (j > 0 && tmp < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            --j;
        }

        arr[j] = tmp;
    }
}

void hybridMergeSort(int *arr, int n)
{
    int *tempArr = malloc(n * sizeof(int));
    if (tempArr != NULL)
    {
        if (n > MIN_SIZE)
            mSort(arr, tempArr, 0, n - 1);
        else
            insertionSort(arr, n);

        free(tempArr);
    }
    else
    {
        printf("Error: Out of memory\n");
        exit(1);
    }
}

int main()
{
    int arr[] = { 5, 9, 1, 4, 8, 3, 7, 6, 2 };
    int n = sizeof(arr) / sizeof(int);

    printf("Before sorting:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    hybridMergeSort(arr, n);

    printf("\nAfter sorting:\n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);

    return 0;
}

在上面的代码中，`MIN_SIZE` 定义了插入排序算法的最小规模。如果归并排序的规模小于 `MIN_SIZE`，则使用插入排序算法。在 `hybridMergeSort` 函数中，我们首先分配临时数组 `tempArr`，然后根据数组规模判断使用原地归并排序算法还是插入排序算法。最后，释放临时数组 `tempArr` 的内存。