无序单链表排序算法(c语言版本)

青旅半醒 2022-03-01 03:54 235阅读 0赞

这是一道非常经典的面试题。我们知道，快速排序的思想是，通过一个基准元素(pivot)，一趟排序就将数据划分为两个部分：左边的部分小于该基准元素，右边的部分大于该基准元素。另外，实现快速排序的关键在于随机访问数据元素，所以快速排序通常都是基于数组来实现的，但是面试中往往会要求对无序单链表进行快排，这就明显不能使用快速排序的基本思想，因为从链表尾部无法向链表头部遍历。

解决方法还是基于快速排序思想，但是是快速排序的一个变形方法，参见我前面的博客

[https://blog.csdn.net/tao\_627/article/details/88689382][https_blog.csdn.net_tao_627_article_details_88689382]

该思路的详细解读，参见

[https://blog.csdn.net/u010429424/article/details/77776731][https_blog.csdn.net_u010429424_article_details_77776731]

下面是我的源码实现

//description: 描述无序单链表的节点排序
    //date: 2019-03-20
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    
    typedef struct ListNode {
        int val;
        struct ListNode *next;
    } ListNode;
    
    
    ListNode* CreateListNode(int value){
        ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
        if(pNode == NULL){
            printf("failed to create ListNode\n");
            exit(-1);
        }
    
        pNode->val = value;
        pNode->next = NULL;
        return pNode;
    }
    
    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext){
        if(pCurrent == NULL || pNext == NULL){
            printf("No necessary to connect two nodes\n");
            return;
        }
    
        pCurrent->next = pNext;
    }
    
    void DestroyListNode(ListNode* pNode){
        if(pNode != NULL){
            printf("-----delete list node [%d]-----\n", pNode->val);
            free(pNode);
        }
    }
    
    //在表头节点后面拼接n个随机元素的单链表
    void CreateList(ListNode **pHead, int n){
        if(pHead == NULL || *pHead == NULL){
            printf("Invalid List header ptr\n");
            exit(-1);
        }
    
        int i;
        srand(time(0));
        ListNode *pNew, *pNode = *pHead;
        for(i=0; i<n; i++){
            pNew = (ListNode*)malloc(sizeof(ListNode));
            pNew->val = rand()%100 + 1;
            pNode->next = pNew;
    
            pNode = pNew;
        }
        pNode->next = NULL;
    }
    
    void DestroyList(ListNode* pHead){
        ListNode *pNode = pHead;
        while(pNode != NULL){
            pHead = pNode->next;
            free(pNode);
            pNode = pHead;
        }
    }
    
    void PrintList(ListNode* pHead){
        printf("------------print list begin-----------");
        ListNode* pNode = pHead;
        while(pNode != NULL){
            printf("%d ", pNode->val);
            pNode = pNode->next;
        }
        printf("------------print list end-------------");
    }
    
    //统计链表长度
    int ListSize(ListNode* pHead){
        int len = 0;
        ListNode* pNode = pHead;
        while(pNode != NULL){
            len++;
            pNode = pNode->next;
        }
    
        return len;
    }
    
    ListNode* FindListFoot(ListNode* pHead){
        ListNode* pNode = pHead;
        while(pNode->next != NULL){
            pNode = pNode->next;
        }
    
        return pNode;
    }
    
    //==================业务函数定义到这里=============
    
    void swap(int* a, int* b){
        int t = *a;
        *a = *b;
        *b = t;
    }
    
    //使用快速排序算法来确定基准点的位置节点，这是核心处理函数
    void Partition(ListNode* pBegin, ListNode* pEnd){
        if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
            return;
    
        //定义两个指针
        ListNode* p1 = pBegin;
        ListNode* p2 = pBegin->next;
        int pivot = pBegin->val;
    
        while(p2 != NULL && p2 != pEnd->next){
            if(p2->val < pivot){
                p1 = p1->next;
                if(p1 != p2){
                    swap(&p1->val, &p2->val);
                }
            }
            p2 = p2->next;
        }
        swap(&p1->val, &pBegin->val);
        //此时p1是中值节点
    
        if(p1->val > pBegin->val)
            Partition(pBegin, p1);
        if(p1->val < pEnd->val)
            Partition(p1->next, pEnd);
    }
    
    void QuickSort(ListNode** pHead){
        ListNode* pFoot = FindListFoot(*pHead);
        Partition(*pHead, pFoot);
    }
    
    //==================测试代码=======================
    void Test(char* testName, ListNode** pHead, int* expectedValues, int expectedLength){
        if(testName != NULL)
            printf("%s begins:\n", testName);
    
        //======真正要干的活儿==========
        QuickSort(pHead);
    
        int idx = 0;
        ListNode* pNode = *pHead;
        while(pNode !=NULL && idx < expectedLength){
            if(pNode->val != expectedValues[idx])
                break;
    
            pNode = pNode->next;
            idx++;
        }
    
        if(pNode == NULL && idx == expectedLength)
            printf("%s Passed.\n", testName);
        else
            printf("%s FAILED.\n", testName);
    }
    
    //--------------下面测试一些特例情况--------------
    
    //某些节点是重复的
    void Test1(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(11);
        ListNode* pNode2 = CreateListNode(20);
        ListNode* pNode3 = CreateListNode(3);
        ListNode* pNode4 = CreateListNode(3);
        ListNode* pNode5 = CreateListNode(41);
        ListNode* pNode6 = CreateListNode(4);
        ListNode* pNode7 = CreateListNode(51);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {3, 3, 4, 11, 20, 41, 51};
        Test("Test1", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    //没有节点重复
    void Test2(){
        //构建一个单链表
        ListNode* pNode1 = CreateListNode(1);
        ListNode* pNode2 = CreateListNode(2);
        ListNode* pNode3 = CreateListNode(3);
        ListNode* pNode4 = CreateListNode(4);
        ListNode* pNode5 = CreateListNode(5);
        ListNode* pNode6 = CreateListNode(6);
        ListNode* pNode7 = CreateListNode(7);
    
        ConnectListNodes(pNode1, pNode2);
        ConnectListNodes(pNode2, pNode3);
        ConnectListNodes(pNode3, pNode4);
        ConnectListNodes(pNode4, pNode5);
        ConnectListNodes(pNode5, pNode6);
        ConnectListNodes(pNode6, pNode7);
    
        ListNode* pHead = pNode1;
    
        int expectedValues[] = {1, 2, 3, 4, 5, 6, 7};
        Test("Test2", &pHead, expectedValues, sizeof(expectedValues) / sizeof(int));
    
        //删除该单链表
        DestroyList(pHead);
    }
    
    
    int main(int argc, char** argv){
        Test1();
        Test2();
    
        return 0;
    }

已经测试通过，下面是运行截图

![20190321165427566.png][]

[https_blog.csdn.net_tao_627_article_details_88689382]: https://blog.csdn.net/tao_627/article/details/88689382
[https_blog.csdn.net_u010429424_article_details_77776731]: https://blog.csdn.net/u010429424/article/details/77776731
[20190321165427566.png]: /images/20220301/b134f0a138ec48d78d22411bdedeed74.png