首页 > 代码库 > 链表快速排序

链表快速排序

链表快速排序

大致思想是通过一个指针数组转化为常规数组快速排序,最后再重新梳理链表。

#include <iostream>#include <vector>using namespace std;typedef struct NODE{    int data;    NODE* next;    NODE(int _data) : data(_data), next(nullptr){}}NODE;NODE* createLinkTable(){    const int tableLen = 10;    const int testArray[tableLen] = { 12, 32, 0, 45, 2, 78, 34, 8, 365, 7 };    NODE* root = new NODE(testArray[0]);    NODE* prev = root;    for (int i = 1; i < tableLen; i++)    {        NODE* cur = new NODE(testArray[i]);        prev->next = cur;        prev = cur;    }    return root;}void destroyLinkTable(NODE* table){    NODE* iter = table;    while (iter)    {        NODE* next = iter->next;        delete iter;        iter = next;    }}void sortLinkTable(vector<NODE*>& linkVec,const int left,const int right){    if (left >= right)    {        return;    }    NODE* flag = linkVec[right];    int leftIter = left;    int rightIter = left;    for (int i = left; i < right-1; i++)    {        if (linkVec[i]->data < flag->data)        {            swap(linkVec[leftIter], linkVec[i]);            leftIter++;        }        else{            rightIter++;        }    }    if (linkVec[leftIter]->data > linkVec[right]->data)    {        swap(linkVec[leftIter], linkVec[right]);    }    sortLinkTable(linkVec, left, leftIter-1);    sortLinkTable(linkVec, leftIter + 1, right);}NODE* rebuildLinkTable(vector<NODE*>& linkVec){    NODE* root = linkVec[0];    NODE* prev = root;    for (size_t i = 1; i < linkVec.size(); i++)    {        prev->next = linkVec[i];        prev = linkVec[i];    }    prev->next = nullptr;    return root;}NODE* sortLinkTable(NODE* table){    vector<NODE*> linkVec;    NODE* cur = table;    while (cur)    {        linkVec.push_back(cur);        cur = cur->next;    }    sortLinkTable(linkVec, 0, linkVec.size()-1);    return rebuildLinkTable(linkVec);}void displayLinkTable(const NODE* const table){    const NODE* iter = table;    while (iter)    {        cout << iter->data << " ";        iter = iter->next;    }    cout << endl;}int main(int argc, char* argv[]){    NODE* table = createLinkTable();    if (!table)    {        return -1;    }    displayLinkTable(table);    table = sortLinkTable(table);    displayLinkTable(table);    destroyLinkTable(table);    return 0;}