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

喜欢ヅ旅行 2022-12-29 04:48 116阅读 0赞

## 1.插入排序 ##

链表的创建等系列操作代码详见[单链表实现][Link 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

[Link 1]: https://blog.csdn.net/weixin_43054397/article/details/84076882