插入排序，从尾部插入

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素插入到已经排好序的序列中。从尾部插入的插入排序实现方法如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5，直到所有元素都被排序完成

代码实现如下：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        # 待插入的元素
        key = arr[i]
        # 已排序序列的末尾索引
        j = i - 1
        # 从后向前扫描已排序序列
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 插入到正确位置
        arr[j + 1] = key
    return arr

时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

相关问题

插入排序算法算法设计

插入排序算法的基本思想是每次将一个待排序的元素，按其大小插入到已经排好序的子序列的适当位置，直到全部元素插入完成为止。具体实现时，插入排序会将序列分为两部分：头部是已经排序完毕的，尾部是待排序的状态。从头开始扫描每一个元素，每当扫描一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序。插入排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。

以下是Java实现插入排序算法的代码：

public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < arr.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }
}

单链表直接插入排序c

以下是单链表直接插入排序的C语言实现：

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 定义链表结构体
typedef struct List {
    Node *head;
    int length;
} List;

// 初始化链表
void initList(List *list) {
    list->head = NULL;
    list->length = 0;
}

// 在链表尾部插入节点
void append(List *list, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (list->head == NULL) {
        list->head = newNode;
    } else {
        Node *p = list->head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }
    list->length++;
}

// 打印链表
void printList(List *list) {
    Node *p = list->head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 单链表直接插入排序
void insertSort(List *list) {
    if (list->head == NULL || list->head->next == NULL) {
        return;
    }

    Node *p = list->head->next;
    list->head->next = NULL;

    while (p != NULL) {
        Node *q = list->head;
        Node *pre = NULL;

        while (q != NULL && q->data < p->data) {
            pre = q;
            q = q->next;
        }

        if (pre == NULL) {
            list->head = p;
        } else {
            pre->next = p;
        }

        Node *tmp = p->next;
        p->next = q;
        p = tmp;
    }
}

int main() {
    List list;
    initList(&list);

    // 在链表尾部插入节点
    append(&list, 3);
    append(&list, 1);
    append(&list, 4);
    append(&list, 2);
    append(&list, 5);

    printf("排序前：");
    printList(&list);

    // 单链表直接插入排序
    insertSort(&list);

    printf("排序后：");
    printList(&list);

    return 0;
}