直接插入排序C++

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

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

这个算法的时间复杂度为O(n^2)，适用于小规模数据的排序。

相关问题

直接插入排序c++

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

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

        /* Move elements of arr[0..i-1], that are
           greater than key, to one position ahead
           of their current position */
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

这是一个基本的直接插入排序算法，它的时间复杂度为 O(n^2)，适用于小规模数据的排序。

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