写这个主要是为了面试吧. 复习下链表操作, 既然链表快排就是拿来交互指针的, 交互数据数据部分过大拷贝消耗怎么办? 网上一些实现在这方面比较 扯淡. 怎么好多直接 swap(value1, value2) 的...
数组快排比较好写, 就是要方便, 一种取巧的方法 (本文不是这种方法), 一个数组, 每个数组是一个结构体, 包括指针, 和对应拿来比较的值. 这样拿去数组快排, 然后按照快排后数组的指针信息重建链表. 需要的额外空间就不大了.
下面是传统的递归快排. 快排选择比 key 小的在 key 前面全都用指针交换实现.
- #include <bits/stdc++.h>
- using namespace std;
- struct LinkNode {
- int val;
- LinkNode *next;
- LinkNode(int _v = 0):val(_v), next(nullptr) {}
- };
- LinkNode* init_random_list(const vector<int>& init_list) {
- if(init_list.size() == 0) {
- return nullptr;
- }
- auto it = init_list.begin();
- LinkNode *head = new LinkNode(*it);
- LinkNode *tmp = head;
- for(++it; it != init_list.end(); it++ ) {
- tmp->next = new LinkNode(*it);
- tmp = tmp->next;
- }
- return head;
- }
- void print_linklist(LinkNode *p) {
- bool first = true;
- while(p) {
- if(first) {
- first = false;
- } else {
- printf(" ");
- }
- cout <<p->val;
- p = p->next;
- }
- cout <<endl;
- }
- void quick_sort(LinkNode *lef, LinkNode *rig) {
- if(lef->next == rig) {
- return ;
- }
- LinkNode* p = lef, *q, *pos = lef->next;
- while(p->next != rig) {
- if(p->next->val <pos->val) {
- q = p->next;
- p->next = q->next;
- q->next = lef->next;
- lef->next = q;
- } else {
- p = p->next;
- }
- }
- quick_sort(lef, pos);
- quick_sort(pos, rig);
- }
- LinkNode* sort_linklist(LinkNode *p) {
- LinkNode* head = new LinkNode(), *q;
- head->next = p;
- quick_sort(head, nullptr);
- q = head;
- head = head->next;
- delete q;
- return head;
- }
- void delete_link(LinkNode *p) {
- if(p == nullptr) {
- return ;
- }
- delete_link(p->next);
- delete p;
- }
- int main()
- {
- int n;
- while(~scanf("%d", &n)) {
- LinkNode *head = nullptr, *p = head;
- for(int i = 1; i <= n; i++ ) {
- int x;
- scanf("%d", &x);
- if(head == nullptr) {
- head = new LinkNode(x);
- p = head;
- } else {
- p->next = new LinkNode(x);
- p = p->next;
- }
- }
- head = sort_linklist(head);
- print_linklist(head);
- delete_link(head);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2967050.html