单链表的排序（插入，选择，冒泡）-蒲公英云

单链表的排序（插入，选择，冒泡）

1.插入排序

链表的创建等系列操作代码详见单链表实现

void Insert_Sort(LinkList &L) {   // 插入排序，变更结点连接
    Node *p = L->next, *head;  // p指针指向每次要插入的结点，head指针用于找到插入的位置
    Node *temp = p->next;      // temp指针 指向 p指针后继结点，避免断链
    p->next = NULL;            // 构造一个结点的有序表
    p = temp;                  
    while( p!= NULL ) { 
        temp = p->next;        // 保存 p指针后继结点
        head = L;              
        while ( head->next != NULL && p->data > head->next->data)
            head = head->next;         // 有序表中查找插入的位置
        p->next = head->next;          
        head->next = p;
        p = temp;
    }
}

2.选择排序

void Select_Sort1(LinkList &L){   // 选择排序，变更结点连接
    Node *head = L, *p = head->next;  
    head->next = NULL;   
    for ( ; p!=NULL; ) { 
        Node *minn = p, *min_pre;   // *minn指向最小值结点, *min_pre指向*minn前一个，便于删除操作
        for ( Node *q = p; q->next!=NULL; q = q->next) { 
            if ( minn->data > q->next->data ) { 
                minn = q->next;
                min_pre = q;
            }
        }
        if( minn!=p)  min_pre->next = minn->next; // 在当前链表中删除minn结点
        else  p = p->next;     //只有当minn==p，将p插入有序表时才需将p指向后继结点
        minn->next = NULL;
        head->next = minn;    // 将minn结点插入到新有序表最后一位
        head = head->next;
    }
}
void Select_Sort2(LinkList &L){      // 选择排序，交换结点数据
    for ( Node *p = L->next; p->next!=NULL; p = p->next) { 
        Node *minn = p;
        for ( Node *q = p->next; q!=NULL; q = q->next) { 
            if( minn->data > q->data ) { 
                minn = q;
            }
        }
        if( minn != p ) { 
            ElemType t = minn->data;
            minn->data = p->data;
            p->data = t;
        }
    }
}

3.冒泡排序

void Bubble_Sort(Node *head){    // 冒泡排序，交换结点数据
    for ( Node *temp = head->next; temp->next != NULL; temp = temp->next ){ 
        for ( Node *p = head->next; p->next != NULL; p = p->next){ 
            if ( p->data > p->next->data ) { 
                ElemType t = p->data;
                p->data = p->next->data;
                p->next->data = t;
            }
        }
    }
}

实现

#include<stdio.h>
#include<malloc.h>
#include<time.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct node{ 
    ElemType data;
    node *next;
}Node,*LinkList;
Status CreatList(LinkList &L,int n){ //创建链表
    LinkList p,q;
    int i;
    L = (LinkList)malloc(sizeof(Node));
    q =L;
    for(int i=0; i<n; i++){ 
        p = (LinkList)malloc(sizeof(Node));
        scanf("%d",&p->data);
        q->next = p;
        q = p;
    }
    q->next = NULL;
    return OK;
}
void ListTraverse(LinkList L){ //遍历链表
    if(L->next == NULL)
        printf("LinkList is empty!!!");
    else{ 
        LinkList p;
        p = L->next;
        while(p!= NULL){ 
            printf("%d ",p->data);
            p = p->next;
        }
        printf("\n");
    }
}
void Bubble_Sort(Node *head) {   //冒泡排序，交换结点数据
    for ( Node *temp = head->next; temp->next != NULL; temp = temp->next ){ 
        for ( Node *p = head->next; p->next != NULL; p = p->next){ 
            if ( p->data > p->next->data ) { 
                ElemType t = p->data;
                p->data = p->next->data;
                p->next->data = t;
            }
        }
    }
}
void Select_Sort2(LinkList &L){   // 选择排序，交换结点数据
    for ( Node *p = L->next; p->next!=NULL; p = p->next) { 
        Node *minn = p;
        for ( Node *q = p->next; q!=NULL; q = q->next) { 
            if( minn->data > q->data ) { 
                minn = q;
            }
        }
        if( minn != p ) { 
            ElemType t = minn->data;
            minn->data = p->data;
            p->data = t;
        }
    }
}
void Select_Sort1(LinkList &L){   // 选择排序，变更结点连接
    Node *head = L, *p = head->next;  
    head->next = NULL;   
    for ( ; p!=NULL; ) { 
        Node *minn = p, *min_pre;   
        for ( Node *q = p; q->next!=NULL; q = q->next) { 
            if ( minn->data > q->next->data ) { 
                minn = q->next;
                min_pre = q;
            }
        }
        if( minn!=p)  min_pre->next = minn->next; 
        else  p = p->next;  
        minn->next = NULL;
        head->next = minn;  
        head = head->next;
    }
}
void Insert_Sort(LinkList &L) {   // 插入排序，变更结点连接
    Node *p = L->next, *head;
    Node *temp = p->next;
    p->next = NULL;
    p = temp;
    while( p!= NULL ) { 
        temp = p->next;
        head = L;
        while ( head->next != NULL && p->data > head->next->data)
            head = head->next;
        p->next = head->next;
        head->next = p;
        p = temp;
    }
}
int main(){ 
    LinkList L;
    printf("输入10个数:\n");
    CreatList(L,10);
    printf("初始化10个元素,分别是:\n");
    ListTraverse(L);
    Select_Sort1(L);
    printf("升序排序输出链表:\n");
    ListTraverse(L);
    return OK;
}
 // 23 12 13 44 55 21 89 76 67 9