用双链表快速排序
#include<cstdio>
#include<fstream>
#include<iostream>
using namespace std;
struct Node {
int data = 0;
Node* l = NULL, * r = NULL;
}*head = NULL , *tail = NULL;
void N_swap(Node* a, Node* b) {
int tmp = a->data;
a->data = b->data;
b->data = tmp;
}
void quick_sort(Node *h, Node* t,int l, int r) {
if (l < r) {
Node* p = h, * q = t;
int x = h->data, p1 = l , q1 = r;
while (p1 < q1) {
if (p->data == q->data) {
q = q->l, q1--;
continue;
}
while (p->r && p->data < x) p = p->r, p1++;
while (q->l && q->data > x) q = q->l, q1--;
if (p1 < q1) N_swap(p, q);
}
quick_sort(h, q, l, q1), quick_sort(q->r, t, q1 + 1, r);
}
}
int main() {
ifstream ifile("in.txt");
int x;
while (ifile >> x) {
Node* p = new Node;
p->data = x;
if (head) {
tail->r = p;
p->l = tail;
}
else head = p;
tail = p;
}
int l = 0;
for (Node* i = head; i; i = i->r) cout << i->data << " ",l++;
puts("");
quick_sort(head, tail, 1, l);
for (Node* i = head; i; i = i->r) cout << i->data << " ";
puts("");
return 0;
}