单链表排序-蒲公英云

单链表排序

小咪咪 2022-05-08 07:00 350阅读 0赞

算法思想：采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后一次扫描剩下的结点p(直至p==NULL为止)，在有序表中通过比较查找插入p的前驱结点pre,然后将p插入到*pre之后
核心代码

void Sort(LinkList *L){
    LinkList *p,*r,*pre;
    p=L->next;
    r = p->next;   //保持r是p的后继结点,以保证不断链
    p->next = NULL; //构造一个只有一个数据结点的有序表 就是让一个有序表的长度为1
    p=r;
    while(p){
        r=p->next;  //保存p的后继结点指针
        pre = L;
        while(pre->next!=NULL && pre->next->data < p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r;  //扫描剩下的结点
    }
display(L);
}

运行代码

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
struct LinkList{
    int data;
    struct LinkList *next;
};
void display(LinkList *L){
    if (L->next)
    {
        printf("%d ",L->next->data);
        display(L->next);
    }else{
        printf("\n");
    }
}
void Sort(LinkList *L){
    LinkList *p,*r,*pre;
    p=L->next;
    r = p->next;   //保持r是p的后继结点,以保证不断链
    p->next = NULL; //构造一个只有一个数据结点的有序表 就是让一个有序表的长度为1
    p=r;
    while(p){
        r=p->next;  //保存p的后继结点指针
        pre = L;
        while(pre->next!=NULL && pre->next->data < p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r;  //扫描剩下的结点
    }
display(L);
}
int main(){
    LinkList *L = (struct LinkList *)malloc(sizeof(struct LinkList));
    int a[] = {1,5,2,7,4,7,8,54,8,34,8,3,8,3};
    int n = sizeof(a)/(sizeof(int));
    int h = 0;
    L->next = NULL;
    LinkList *p;
    for (int i=0;i<n;i++)
    {
        p = (struct LinkList *)malloc(sizeof(struct LinkList));
        p->data =a[h++];
        p->next = L->next;
        L->next = p;
    }
Sort(L);
    return 0;
}