一.廢話不多說，直接上代碼。如果想看雙向循環(huán)鏈表的朋友，可以在我的博客里找。

你好

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

typedef struct node
{
    int data;
    struct node *next;
}node;

//生成一個節(jié)點
node *initList(void)
{
    node *new = malloc(sizeof(node));

    if(!new)
    {
        printf("malloc fail!\n");
        return NULL;
    }

    new->data = 0;
    new->next = NULL;

    return new;
}

//頭插法
void head_insert(node *head, node *new)
{
    new->next = head->next;
    head->next = new;
}

//遍歷
node *traverse(node *head)
{
    for(node *p = head->next; p; p = p->next)
    {
        printf("%d ", p->data);
    }

    printf("\n");
}


//冒泡排序，最優(yōu)版本
void bubble_sort(node *head)
{
    int flag;
    node  *p, *prev, *tail;

    tail = NULL;   //tail以及tail后面的是排好序的元素，第一次還沒有排好，所以為NULL
    
    while(1)
    {
        flag = 1;   //flag用來標(biāo)志是否已經(jīng)排好序

        //每次從head->next開始遍歷，直到tail結(jié)束, prev是p的前驅(qū)節(jié)點
        for(prev = head, p = head->next; p && p->next != tail; prev = prev->next)
        {
            //交換后，p已經(jīng)移動到后面，不需要再遍歷下一個
            if(p->data > p->next->data)
            {
                flag = 0;      //修改flag=0，標(biāo)志本輪循環(huán)交換過
                prev->next = p->next;    //彈出p節(jié)點
                p->next = p->next->next; //插入p節(jié)點
                prev->next->next = p;    //原來的p->next已經(jīng)修改，需要用prev->next代替
            }
            else //沒有交換就繼續(xù)遍歷下一個
            {
                p = p->next;
            }
        }
        
        printf("本輪排序移動出的最大值：%d\n", p->data);
        traverse(head);   顯示每一輪排序結(jié)果

        if(flag)   //如果內(nèi)層循環(huán)中都沒有交換過，則所有節(jié)點都已經(jīng)是排好序的
        {
            printf("冒泡排序結(jié)束！\n");
            break;
        }

        tail = p;  //tail向前移一個，tail以及tail后面的是排好序的元素
    }
}

//選擇排序,初級版本
void choose_sort1(node *head)
{
    node *p, *q, *max, *prior;
    
    p = malloc(sizeof(node));  //生成一個p節(jié)點
    p->next = head->next;      //p取代head
    head->next = NULL;         //head是空鏈表
    
    while(p->next)
    {
        prior = p;
        max = prior->next;

        for(q = max; q->next; q = q->next)
        {
            if(max->data < q->next->data)
            {
                max = q->next;
                prior = q;
            }
        }
        
        //從p鏈表中彈出一個最大的節(jié)點，用頭插法插入到head鏈表中
        prior->next = max->next;  
        max->next = head->next;
        head->next = max;
    }

    free(p);
}

//選擇排序,最優(yōu)版本
void choose_sort(node *head)
{
    node *q, *min, *prev, *tail;
    
    //tail及tail前面是排好序的，每次從tail后面選出一個最小值，插入到tail前面，直到等于NULL結(jié)束
    //要額外保證p->next!=NULL,因為內(nèi)層循環(huán)q=p->next; 用q->next來判斷是否為空,可能會越界
    for(tail = head; tail && tail->next; tail = tail->next)
    {
        //prev是min的前驅(qū)節(jié)點，q用來遍歷，從min->next直到head鏈表最后一個
        for(prev = tail, min = tail->next, q = tail->next; q->next; q = q->next)
        {
            if(min->data > q->next->data) //找到一個更小的節(jié)點，就記錄
            {
                min = q->next;     
                prev = q;         //單鏈表要額外記錄min的前驅(qū)節(jié)點
            }
        }

        printf("本輪排序選擇出的最小值：%d\n", min->data);
        if(min != tail->next)   //如果找到比min更小的節(jié)點，就插入到p后面
        {
            prev->next = min->next;
            min->next = tail->next;
            tail->next = min;
        }

        traverse(head);   //顯示每一輪排序結(jié)果
    }
}

//插入排序，最優(yōu)版本
void insert_sort(node *head)
{
    //頭結(jié)點是空的或者表是空的或者表只有一個節(jié)點時候不用排
    if(!head || !head->next||!head->next->next) 
    {
        return;
    }

    node *p, *q, *tail;

    //head->next->next開始遍歷，tail及tail前面的是排好序的,p是本輪待插入值, p是NULl時結(jié)束
    for(tail = head->next, p = tail->next; p; p = tail->next)
    {
        //從head->next開始遍歷，直到tail結(jié)束
        for(q = head; q != tail; q = q->next)
        {
            if(p->data < q->next->data) //把插入后結(jié)束本次遍歷
            {
                tail->next = p->next;

                p->next = q->next;
                q->next = p; 
                break;
            }
        }

        printf("本輪排序插入值：%d, ", p->data);

        if(tail == q)   //在tail前面沒有插入，就下移
        {
            printf("已處于插入位置\n");
            tail = tail->next;
        }
        else
        {
            //p已經(jīng)處于插入位置，顯示時需要用p->next->data
            printf("插入到%d的前面\n", p->next->data);
        }

        traverse(head);  //顯示每一輪排序結(jié)果
    }
}

//快速排序的每一次劃分
node *partition(node *head, node *tail)
{
    //頭結(jié)點是空的或者表是空的或者表只有一個節(jié)點時候不用排
    //已經(jīng)在調(diào)用函數(shù)前判斷好了，進來的鏈表都是至少有兩個元素的
    node *p, *prev, *basic; 

    basic = head->next;  //basic是基準(zhǔn)點

    //從baisc后面開始遍歷，找到比baisc小的就插入到head后面，直到tail結(jié)束，prev是p的前驅(qū)節(jié)點
    //這里head可以理解為本次待劃分的鏈表的頭結(jié)點，tail是鏈表的最后一個節(jié)點的下一個可以理解為NULL
    for(prev = basic, p = basic->next; p && p != tail; p = prev->next)
    {
        if(basic->data > p->data)  //用頭插入法把所有比baisc小插入到head后面
        {
            prev->next = p->next;
            p->next = head->next;
            head->next = p;
        }
        else  //沒有找到比basic小的就一直后移，prev與p同時后移
        {
            prev = prev->next;  
        }
    }

    return basic;  
}

//快速排序
void quick_sort(node *head, node *tail)
{
    //頭結(jié)點是空的或者表是空的或者表只有一個節(jié)點時候不用排
    //tail是鏈表的結(jié)束點，一開始等于NULL,后面等于basic
    if(!head || head->next == tail || head->next->next == tail)
    {
        return ;
    }
   
    //baisc前的節(jié)點都比basic小，baisc后的節(jié)點都比baisc大
    node *basic = partition(head, tail);  
    printf("本次劃分節(jié)點：%d\n", basic->data);

    quick_sort(head, basic); //把head->next到basic前一個進行遞歸排序
    quick_sort(basic, tail); //從basic->next到tail前一個進行遞歸排序
}

int main(void)
{
    int i, len;
    node *head, *new, *p, *q;

    printf("請輸入單鏈表的長度: ");
    scanf("%d", &len);

    head = initList();
    head->data = len;

    printf("請輸入元素：");
    for(int i = 0; i<len; i++)
    {
        new = initList();
        scanf("%d", &new->data);
        head_insert(head, new);
    }

    printf("請選擇排序方式，1.選擇排序 2.冒泡排序 3.插入排序 4.快速排序: ");
    scanf("%d", &i);
    
    printf("排序前:\n");
    traverse(head);
    switch(i)
    {
        case 1:
            choose_sort(head);
            break;
        
        case 2:
            bubble_sort(head);
            break;

        case 3:
            insert_sort(head);
            break;

        case 4:
            quick_sort(head, NULL);
            break;
    }

    printf("由小到大排序后:\n");
    traverse(head);
    
    return 0;
}

? ? ? ?

溫馨提示：

????????如果復(fù)制時發(fā)現(xiàn)有縮進報錯，后者空格報錯等問題，以VScode為例，可以按Ctrl+F，復(fù)制一個報錯的空格，然后替換成一個手打的空格鍵，具體操作可以搜搜，可以看我的博客。

具體截圖：以 12 34 78 56 23 99 34 12 45 76為例，其他朋友可以自己舉

選擇排序

冒泡排序

插入排序

快速排序

二.代碼分析

? ? ? ? 如果你認真看完上述的代碼和注釋，那么，我可以大概率保證你基本可以看懂了單鏈表的排序，其實也不難，就是在關(guān)鍵步驟和控制條件。下面來仔細分析每個排序的關(guān)鍵步驟和控制條件。

冒泡排序

? ? ? ? 思路：冒泡排序就是從首元結(jié)點開始，左右兩兩比較大小，以從小到大排序為例，如果比后面一個的節(jié)點大，就交換，然后繼續(xù)往后比較，直到到達已經(jīng)排好的元素為止。

? ? ? ? 特點：每一輪冒泡排序結(jié)束后，總會把最大的節(jié)點放到最后面，不斷的往前移，直到頭結(jié)點，就結(jié)束了。

? ? ? ? 注意的地方：單鏈表的交換，不同于數(shù)組的交換，單鏈表的交換后，以p和q為例，p在q的前面，如果p->data > q->data,就交換p和q節(jié)點，交換后p已經(jīng)處于下一次待交換的位置，所以不需要在p = p->next了，否則會漏了一個沒排，出錯，需要特別注意!

? ? ? ? 優(yōu)化地方：1.設(shè)置flag，來標(biāo)志鏈表中的元素是否已經(jīng)是排好序的，因為這里做可以用一次循環(huán)判斷出鏈表中的元素是否已經(jīng)排好，而不用進行無用的多層循環(huán)。2.設(shè)置一個tail，來指明后面的節(jié)點是排好的，當(dāng)遍歷到tail時，就結(jié)束本輪循環(huán)，同時tail前移一個。

選擇排序

? ? ? ? 思路：選擇排序就是每次從未排好的節(jié)點中，通過遍歷比較大小的方法，選擇出一個最小的（以從小到大排為例），然后插入到排好的后面，這樣，每輪循環(huán)就可以選出一個最小的，直到全部插入完為止。

? ? ? ? 特點：跟插入排序很像，但兩者略有不同，選擇排序先選出最小的，然后直接插入到排好元素的后面，而插入排序是直接選出一個節(jié)點，然后通過和排好的元素進行比較大小來插入到合適的位置。

? ? ? ? 注意的地方：以從小到大排為例，采用尾插法應(yīng)該是每次選取最小的，如果采用頭插法應(yīng)該是每次選取最大的。

? ? ? ? 優(yōu)化地方：如果這個節(jié)點本來就處于待插入地方，即當(dāng)前最小的，就不需要交換了，直接進行下一輪。寫了兩版本的一個是生成一個p節(jié)點來取代head頭結(jié)點, 然后直接把每次選擇出的節(jié)點直接插入到后面，然后再重新讓head取代p指向排好序的節(jié)點。另外一個版本的是設(shè)置一個tail標(biāo)志，之所以說有點像插入排序，就是體現(xiàn)在這里了。

插入排序

? ? ? ? 思路：插入排序就是每次直接從未排好序的節(jié)點中拿一個出來，一般是下一個；然后在排好序的節(jié)點中通過遍歷的方法來比較應(yīng)該插入到的位置，直到插完為止。

? ? ? ? 特點：直接選一個插入，不像選擇排序那樣，先選了，再插入。

? ? ? ? 注意的地方：需要設(shè)置標(biāo)志tail來指明已經(jīng)排好的節(jié)點的界限，遍歷查找插入位置時，遇到tail，說明待插入節(jié)點是已經(jīng)排好的節(jié)點中最大的，不需要插入，同時tail要后移一個。

? ? ? ? 優(yōu)化地方：tail標(biāo)志和直接插入。

快速排序

? ? ? ? 思路：每次選中一個基準(zhǔn)點，然后從基準(zhǔn)點后面開始遍歷，如果找到比基準(zhǔn)點小節(jié)點（以從小到大排為例），就插入到基準(zhǔn)點前面，直到鏈表的尾部，結(jié)束。這樣每一次劃分后，處于基準(zhǔn)點前面的節(jié)點都比基準(zhǔn)點小，處于基準(zhǔn)點后面的節(jié)點都比基準(zhǔn)點大。然后分別遞歸劃分基準(zhǔn)點前的節(jié)點和后的節(jié)點。

? ? ? ? 特點：每次劃分結(jié)束后能找到一個基準(zhǔn)點，可以看成是中位數(shù)，然后遞歸。有點像二分查找，跟一顆二叉樹差不多。

? ? ? ? 注意的地方：第一次傳參數(shù)時，傳head(頭節(jié)點）和NULL。而且需要嚴(yán)格控制退出條件，頭結(jié)點為空，或者沒有節(jié)點，或者只有一個節(jié)點時，不用排，直接返回。

? ? ? ? 優(yōu)化的地方：沒啥好講的，還有另外一種劃分方法，就是數(shù)組常用的，就是往中間靠的方法，一個head和tail,如果head<tail，tail就一直往前移，然后如果head<tail,head就一直往后移，直到head == tail是就是本次劃分的基準(zhǔn)點。詳情可以看我的博客里的雙向循環(huán)鏈表排序。由于這里是單鏈表，tail往前移后花費很大的代價，所以不采用，雙向循環(huán)鏈表有前指針prev,可以采用。

三.總結(jié)

? ? ? ? 單鏈表的排序相比數(shù)組的排序來說，是相對困難的，主要是在元素方面，數(shù)組不用考慮什么，直接交換元素，而鏈表相對靈活，一般是交換節(jié)點。如果你寫的鏈表是用交換元素的方式的，我只能說，你寫了假的的鏈表排序，因為你拋棄了鏈表的靈魂。鏈表的交換節(jié)點一般是插入的方法，頭插后者尾插，同時還得記錄一下前驅(qū)節(jié)點的位置，筆者為了優(yōu)化算法，下了很大功夫，在排序中盡量在記錄前驅(qū)節(jié)點的同時，盡量少記錄待交換節(jié)點（前驅(qū)節(jié)點的下一個節(jié)點）。

? ? ? ? 如果你會寫單鏈表的排序，那么我可以說，你一定會寫雙向循環(huán)鏈表的排序，因為基本可以直接復(fù)制過來，只是把判斷鏈表最后一個節(jié)點的條件由NULL改成head而已，因為循環(huán)嘛，最后一個節(jié)點的下一個就是頭結(jié)點了，而單鏈表的最后一個節(jié)點的下一個就是NULL了。

? ? ? ? 想看雙向循環(huán)鏈表的朋友可以去我的博客里看。最后希望朋友你可以給我一個點贊，收藏，評論和轉(zhuǎn)發(fā)，你們的支持是我最大的動力。如果有講錯的地方，請朋友大膽指出，謝謝！畢竟剛開始寫博客。絕對原創(chuàng)！文章來源地址http://www.zghlxwxcb.cn/news/detail-770041.html

到了這里，關(guān)于C語言版--單鏈表排序，冒泡排序，選擇排序，插入排序，快速排序，應(yīng)有盡有，保證看懂，沒有bug!交換節(jié)點版本！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！