首页 > 代码库 > 链表快速排序
链表快速排序
链表快速排序
大致思想是通过一个指针数组转化为常规数组快速排序,最后再重新梳理链表。
#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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。