單連結串列的快速排序

NO IMAGE

單連結串列的特點是:單向。設頭結點位head,則最後一個節點的next指向NULL。如果只知道頭結點head,請問怎麼將該連結串列排序?
設結點結構為:

struct Node{
int key;
Node* next;
};

那麼一般人見到這種題目,立馬就會想到指標交換。是的,大家被指標交換的題目做多了,形成思維定勢了。對於這道題,我們完全可以利用值交換來達到排序的目的。

很多人得第一想法就是選擇排序,這個木有問題,不過它的複雜度為O(n^2);有木有更好一點的方法呢?歸併,不錯,歸併確實能將複雜度降到O(nlogn)不過,它是是連結串列交換的形式,我們這裡提到的是要用值交換的形式。還有別的方法嗎?對了,快排!

你可能回詫異,怎麼會是快排?快排不是需要一個指標指向頭,一個指標指向尾,然後兩個指標相向運動並按一定規律交換值,最後找到一個支點使得支點左邊小於支點,支點右邊大於支點嗎(這句話很長,累死俺了)?是滴,木有錯,不過問題出來了。如果是這樣的話,對於單連結串列我們沒有前驅指標,怎麼能使得後面的那個指標往前移動呢?所以這種快排思路行不通滴,如果我們能使兩個指標都往next方向移動並且能找到支點那就好了。怎麼做呢?

演算法:

1. 支點的選取,由於不能隨機訪問第K個元素,因此每次選擇支點時可以取待排序那部分連結串列的頭指標。
2. 遍歷連結串列方式,由於不能從單連結串列的末尾逆向遍歷,因此使用兩個指標分別向前遍歷的策略,事實上,可以可以採用一趟遍歷的方式將不大於支點的元素放到單連結串列的左邊,把不小於支點的元素都放到單連結串列的右邊。具體方法為:
1)定義兩個指標p, q,其中p指單連結串列頭結點,q指向單連結串列頭結點的下一個結點;
2)使用q遍歷單連結串列,每遇到一個比支點小的元素,就{令p=p->next,然後q和p進行資料交換}。
3. 交換方式,只需節點的值交換,而不是交換指標。

如下圖所示:

既然兩個指標都是從前往後遍歷,那麼連結串列值進行交換就簡單了。找到支點後,支點左邊和支點右邊進行子問題遞迴,就回到快排原來的思路上去了。
程式碼如下:

struct Node 
{
int key;
Node* next;
Node(int nKey, Node* pNext)
: key(nKey)
, next(pNext)
{}
};
Node* GetPartion(Node* pBegin, Node* pEnd)
{
int key = pBegin->key;
Node* p = pBegin;
Node* q = p->next;
while(q != pEnd)
{
if(q->key<key)
{
p = p->next;
swap(p->key,q->key);
}
q = q->next;
}
swap(p->key,pBegin->key);
return p;
}
void QuickSort(Node* pBeign, Node* pEnd)
{
if(pBeign != pEnd)
{
Node* partion = GetPartion(pBeign,pEnd);
QuickSort(pBeign,partion);
QuickSort(partion->next,pEnd);
}
}

使用時只需呼叫QuickSort(pHead,NULL)即可!