[数据结构]单向链表插入排序(C语言)

2023-01-18 21:09:12 来源：博客园

(资料图)

插入排序

插入排序回顾

我们先回顾一下对数组的插入排序，其步骤大致为:先将第一个数据元素看作是一个有序序列，后面的 n-1 个数据元素看作是未排序序列。对后面未排序序列中的第一个数据元素在这个有序序列中进行从后往前扫描，找到合适的插入位置并插入到其中，每次有序序列的长度 +1。

重复这样的操作，将每个未排序序列中的元素插入到当前有序序列中合适的位置。直到未排序序列长度为 0，最后得到一个完整的有序序列，即为排序的结果。

之前写过插入排序的随笔，更多详情点这里插入排序

单向链表的插入排序

单向链表插入排序原理

对于链表的插入排序，原理和普通的插入排序是差不多的。不过要注意的是，在单向链表中，由于链表只能正向遍历，所以在寻找某个节点的合适插入位置时，只能从前向后扫描。

在单向链表插入排序的过程中，我们将前面看成有序链表，将有序链表和无序链表分离，将后面无序链表中的节点不断插入到有序链表中。我们用 node来标记当前待排序的节点，由于插入排序过程中将有序链表和无序链表进行了分离，所以还需要一个 nex来标记下一个待排序节点。同时还需要 pre用于在有序链表中扫描寻找合适插入位置。

单向链表插入排序步骤

单向链表插入排序的大致步骤为：

（1）先将单个节点 node的 next置NULL，形成初始有序链表；（2）pre在有序链表中扫描，nex标记下一个待排序节点，当 pre的 next指向的节点大于等于 node->data时停止；（3）在有序链表中插入节点 node；（4）将 node指向之前暂存的下一个待排序节点 nex，重复步骤（2）（3）。

单向链表插入排序图解

待排序的单向链表

单向链表插入排序核心代码

//插入排序void InsertSort(Linklist *head){    if(!head->next) return;    Linklist *node = head->next, *nex = node->next, *pre;    node->next = NULL;    //单个节点形成初始有序链表    node = nex;    while(node){pre = head;       //pre在有序链表中找到何时插入位置nex = node->next; //暂存下一个待排序节点//找到何时插入位置，pre指向有序链表中最后一个小于node的节点while(pre->next && pre->next->data < node->data)pre = pre->next;//表中插入node->next = pre->next;pre->next = node;node = nex;       //node指向下一个待排序节点    }}

完整程序

完整程序源代码

#include #include #include typedef int Elemtype;        //数据类型typedef struct Node {Elemtype data;           //结构体数据域struct Node *next;       //结构体指针域} Linklist;//链表的初始化Linklist* Initial_linklist(){//向系统申请内存Linklist *head = (Linklist *)malloc(sizeof(Linklist));head->next = NULL;return head;}//创建初始链表  采用尾插法void Create_linklist(Linklist *head, int n) {    //头节点(不带数据)Linklist *node, *end;                        //普通节点 尾节点end = head;                                  //当链表为空时 头尾指向同一个节点printf("创建链表输入 %d 个元素:", n);for (int i = 0; i < n; i++) {                //n为插入普通节点的个数node = (Linklist *)malloc(sizeof(Linklist));scanf("%d", &node->data);end->next = node;                        //当前end的next指向了新节点nodeend = node;                              //end往后移，此时新的节点变成尾节点}end->next = NULL;                            //end最后置NULL}//打印链表void Show_linklist(Linklist *head) {Linklist *t = head->next; //t为遍历指针 访问每个节点数据if (t == NULL)puts("链表为空");while (t != NULL) {printf("%d ", t->data);t = t->next;}printf("\n\n");}//插入排序void InsertSort(Linklist *head){if(!head->next) return;Linklist *node = head->next, *nex = node->next, *pre;node->next = NULL;    //单个节点形成初始有序链表node = nex;while(node){pre = head;       //pre在有序链表中找到何时插入位置nex = node->next; //暂存下一个待排序节点//找到何时插入位置，pre指向有序链表中最后一个小于node的节点while(pre->next && pre->next->data < node->data)pre = pre->next;//表中插入node->next = pre->next;pre->next = node;node = nex;       //node指向下一个待排序节点}}int main(){Linklist *mylist;mylist = Initial_linklist();Create_linklist(mylist, 10);printf("初始状态链表:\n");Show_linklist(mylist);InsertSort(mylist);printf("插入排序后的链表:\n");Show_linklist(mylist);}