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>

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

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

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

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

    return 0;
}

c语言实现插入排序算法

以下是C语言实现插入排序算法的代码：

#include <stdio.h>

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

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

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

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

    return 0;
}

在这个程序中，我们首先定义了一个名为`insertionSort`的函数，该函数接受一个整数数组和数组大小作为输入参数。在该函数中，我们使用了一个`for`循环来遍历数组中的每个元素。在每次迭代中，我们将当前元素存储在一个名为`key`的变量中，并将其前一个元素的索引存储在名为`j`的变量中。

然后，我们使用一个`while`循环来比较`key`和`arr[j]`。如果`arr[j]`大于`key`，则我们将`arr[j]`向右移动一位，直到`arr[j]`小于或等于`key`。最后，我们将`key`插入到正确的位置中，该位置为`j+1`。

在主函数中，我们调用`insertionSort`函数，并输出已排序的数组。