C语言插入排序法是什么？

C语言插入排序法是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序序列中，从而得到一个新的、记录数增加1的有序序列。具体步骤如下：

1. 首先，将待排序的序列分为已排序和未排序两部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余的元素。
2. 从未排序部分取出第一个元素，将其与已排序部分的元素进行比较。
3. 如果该元素小于已排序部分的某个元素，则将该元素插入到该元素的前面。
4. 如果该元素大于或等于已排序部分的所有元素，则将该元素插入到已排序部分的末尾。
5. 重复步骤2-4，直到未排序部分的所有元素都被插入到已排序部分。

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

void insertionSort(int arr[], int n) {
    int i, j, key;
    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;
    }
}

相关问题

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;

        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

这段代码实现了插入排序算法。首先定义了一个`insertionSort`函数，它接受一个整型数组和数组的大小作为参数。在函数内部，使用一个循环遍历数组，将每个元素插入到已排序的子数组中的适当位置。

然后定义了`printArray`函数，用于打印排序后的数组。

在`main`函数中，创建一个整型数组并初始化。然后获取数组的大小，调用`insertionSort`函数对数组进行排序，并最后调用`printArray`函数打印排序后的数组。

运行这段代码，输出结果为：

排序后的数组:
11 12 22 25 64

这是使用插入排序算法对数组进行升序排序的结果。

c语言直接插入排序法链表

直接插入排序法链表的C语言实现如下所示：

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

typedef struct node {
    int data;
    struct node *next;
} Node;

void insertSort(Node **head) {
    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    Node *p, *q, *r;
    p = (*head)->next;
    (*head)->next = NULL;
    while (p != NULL {
        r = pnext;
        q = *head;
        while (q->next != NULL && q->next->data < p->data) {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
        p = r;
    }
}

void printList(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d ", p->data        p = p->next;
    }
    printf("\n");
}

int main() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        Node *p = (Node *)malloc(sizeof(Node));
        p->data = x;
        p->next = head->next;
        head->next = p;
    }
    printf("排序前：");
    printList(head->next);
    insertSort(&head);
    printf("排序后：");
    printList(head->next);
    return 0;
}