c语言直接插入排序法

直接插入排序是一种简单直观的排序算法，它的工作原理类似于打扑克牌整理顺序。其基本步骤如下：

1. **遍历数组**: 从数组的第一个元素开始，将其视为已排序的部分。

2. **查找位置**: 对于未排序部分的第一个元素（称为关键码），依次比较关键码与已排序部分的每个元素，直到找到第一个大于或等于它的元素的位置。

3. **插入**: 如果已找到合适的位置，将关键码移动到该位置，使得比它大的元素都在它后面；如果整个已排序部分都小于关键码，则将其放在最后。

4. **递归过程**: 继续处理未排序部分的下一个元素，重复上述步骤，直至所有元素都被插入到正确的位置，形成有序序列。

**伪代码示例**:

void insertion_sort(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; // 插入到正确位置
   }
}

相关问题

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;
}

c语言编写程序实现直接插入排序法

好的，以下是实现直接插入排序法的 C 代码：

void insertion_sort(int arr[], int n) {
    int i, j, key;

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

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

        arr[j + 1] = key;
    }
}

这个函数接受一个整数数组和数组长度作为参数，并按照直接插入排序法的方法对数组进行排序。

具体的实现方式与 Python 版本类似，首先将当前元素作为关键字 key，然后将它与已排序部分的最后一个元素比较。如果 key 比它小，则将这个元素往后移动一个位置，直到找到一个比 key 小的元素或者已经到达了数组的开始位置。然后将 key 插入到这个位置之后，继续遍历下一个未排序的元素。

这个算法的时间复杂度为 O(n^2)，因为需要对每个元素都进行一次插入操作。不过，它的空间复杂度比较低，只需要使用常数级别的额外空间。