單鏈表快速排序和數(shù)組的快速排序差不多。選一個(gè)樞軸然后進(jìn)行一次劃分把數(shù)字交換到樞軸的兩邊。
這個(gè)過程需要交換，鏈表的交換就有兩種方法盾计，一個(gè)是交換節(jié)點(diǎn)，一個(gè)是直接交換節(jié)點(diǎn)的val值赁遗。交換val值比較方便闯估。
寫快排，一般都是遞歸吼和。
數(shù)組版本的代碼如下。
void quickSort(int a[], int low, int high)
{
if(low < high) //遞歸終止條件
{
//劃分操作
int pivotpos = Partition(a,low,high);
quickSort(a, low, pivotpos-1);//對兩個(gè)子序列排序
quickSort(a, pivotpos+1,high);
}
}
把這個(gè)改成遞歸的版本骑素。
- 輸入?yún)?shù)改一下炫乓， 鏈表給頭和尾就行了刚夺。最開始的鏈表，我們不知道真正的鏈表尾巴是哪個(gè)節(jié)點(diǎn)末捣，但是知道最后一個(gè)節(jié)點(diǎn)的
next一定是NULL侠姑，所以這里輸入的鏈表的范圍是相當(dāng)于從start節(jié)點(diǎn)開始到next為end的節(jié)點(diǎn)結(jié)束。所以：void quickSort(LinkList start, LinkList end)第一次調(diào)用的時(shí)候end為NULL箩做。 - 遞歸終止條件改一下莽红。
start->next != end && start != end所以終止的條件就是start->next == end || start == end，看第一個(gè)條件start->next == end就說明start鏈表里只有一個(gè)start這一個(gè)節(jié)點(diǎn)邦邦。這種情況就不需要排了安吁。第二個(gè)條件start == end就是這個(gè)鏈表里一個(gè)節(jié)點(diǎn)沒有，那也就不用排了燃辖。 -
partition函數(shù)鬼店，數(shù)組版本返回的是樞軸位置的下標(biāo)，鏈表版本就應(yīng)該返回指向樞軸節(jié)點(diǎn)的指針黔龟。 - 接下來就是遞歸調(diào)用妇智。前半段的
start還是start,end變成了mid(樞軸的節(jié)點(diǎn)，因?yàn)檫@里的end是待排序的鏈表最后一個(gè)節(jié)點(diǎn)的next)氏身。后半段的start自然就是mid->next,end還是原來的數(shù)組的end巍棱。
//鏈表
void quickSort(LinkList start, LinkList end)
{
if(start->next != end && start != end)
{
Node * mid = partition(start, end);
quickSort(start, mid);
quickSort(mid->next, end);
}
}
接下來看看關(guān)鍵的劃分是怎么辦。
該貼出來數(shù)據(jù)結(jié)構(gòu)課本上這圖了蛋欣。
有兩個(gè)游標(biāo)航徙，一個(gè)從前往后走，一個(gè)從后往前走豁状，兩個(gè)碰到的位置就是樞軸的最終位置捉偏，一趟劃分結(jié)束。
單項(xiàng)鏈表就沒有游標(biāo)從后往前走這種操作了泻红，所以有這么一種方法夭禽。
選第一個(gè)數(shù)當(dāng)樞軸，一個(gè)指針p記錄比樞軸小的最后一個(gè)數(shù)谊路，另一個(gè)指針q進(jìn)行遍歷讹躯，如果比樞軸大就繼續(xù)便利，如果發(fā)現(xiàn)比樞軸小的值往前換（p先往后挪一下再換缠劝，防止把小數(shù)換后頭去）遍歷到最后潮梯，把第一個(gè)位置的值和p位置的值換一個(gè)下，p這時(shí)候使比樞軸小的數(shù)的最后一個(gè)惨恭，和第一個(gè)的樞軸換一下正好樞軸歸位并且用一個(gè)比樞軸小的數(shù)把第一個(gè)位置填上了秉馏。
Node * partition(LinkList start, LinkList end)
{
Node *p = start;
Node *q = p->next;
printList(start, end);
int pivot = start -> val;
cout << "↑pivot: " << pivot << endl;
while(q!= end)
{
if(q->val < pivot)
{
p = p->next;
swap(p->val, q->val);
}
q=q->next;
}
swap(p->val,start->val);
return p;
}
舉個(gè)栗子
遍歷時(shí)候兩種情況：
- q->val < pivot ： {p = p->next; swap(p->val, q->val); q = q->next; }
- 另一種情況： { q = q->next; }
樞軸等于 4
4 2 5 3 7 9 0 5
↑ ↑
p q
（2比4小， p++ , 換脱羡，q++ 萝究，2換2 ）
4 2 5 3 7 9 0 5
↑ ↑
p q
（5比4大免都， q++ ）
4 2 5 3 7 9 0 5
↑ ↑
p q
（3比4小， p++ , 換帆竹，q++ 绕娘，5換3 ）
4 2 3 5 7 9 0 5
↑ ↑
p q
（7比4大， q++ ）
4 2 3 5 7 9 0 5
↑ ↑
p q
（9比4大栽连， q++ ）
4 2 3 0 7 9 5 5
↑ ↑
p q
（0比4小险领， p++ , 換，q++ 秒紧，0換5 ）
4 2 3 0 7 9 5 5 NULL
↑ ↑
p q
（5比4大绢陌， q++，便利完噩茄，結(jié)束 ）
（然后把p和樞軸換 4換0）
0 2 3 4 7 9 5 5 NULL
↑ ↑
p q
（p就是樞軸位置下面，返回p）
程序截圖。绩聘。沥割。
完整代碼：
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
} Node, *LinkList;
void printList(LinkList l)
{
int sum = 0;
while(l != NULL)
{
cout << l->val <<" ";
sum += l->val;
l = l->next;
}
cout << " sum = "<< sum;
cout << endl;
}
void printList(LinkList s, LinkList e)
{
while(s!= e)
{
cout << s->val<< " ";
s = s->next;
}
cout << endl;
}
LinkList creatList(int *data, int n)
{
LinkList head = new Node(0);
LinkList tail = head;
for(int i = 0; i < n; i++)
{
LinkList n = new Node(0);
n->val = data[i];
tail->next = n;
tail = tail->next;
}
printList(head->next, NULL);
LinkList r = head->next;
delete(head);
return r;
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
Node * partition(LinkList start, LinkList end)
{
Node *p = start;
Node *q = p->next;
printList(start, end);
int pivot = start -> val;
cout << "↑pivot: " << pivot << endl;
while(q!= end)
{
if(q->val < pivot)
{
p = p->next;
swap(p->val, q->val);
}
q=q->next;
}
swap(p->val,start->val);
return p;
}
void quickSort(LinkList start, LinkList end)
{
if(start->next != end && start != end)
{
Node * mid = partition(start, end);
cout << "劃分之后： "<< endl;
printList(start, end);
quickSort(start, mid);
quickSort(mid->next, end);
}
}
int main()
{
//int n = 19;
//int array[n];
/*for(int i = 0; i < n; i++)
{
int t = rand()%n;
array[i] = t;
}*/
int n = 8;
int array[] = {4, 2, 5, 3, 7, 9, 0, 5};
LinkList l = creatList(array, n);
quickSort(l, NULL);
printList(l, NULL);
}
