http://fengchangjian.com/?p=1330

快排最核心的思想就是劃分，確定一個樞軸元素(pivot)，每一趟劃分的目的就是把待排序列分為兩部分，前一部分比樞軸小(序列A)，后一部分比樞軸大(序列B)。經(jīng)過一趟劃分之后序列變?yōu)?#xff1a;{A} pivot {B}。以下是具體步驟：
1、確定每一次劃分的樞軸元素為當(dāng)前待排序列的頭節(jié)點。
2、設(shè)置Slow和Fast兩個游標(biāo)，Slow指向序列A中的最后一個元素，初始化為樞軸本身(待排序列頭節(jié)點)。讓Fast遍歷一遍待排序列，當(dāng)所指元素比樞軸小時，將Slow往前游一格，交換Slow和Fast所指元素的值，這樣仍能保證Slow指向的元素是序列A中的最后一個元素。
3、交換Slow所指元素和樞軸元素的值。
4、對序列A和B重復(fù)步驟1～4。

下面是單鏈表快速排序算法的Java實現(xiàn):
1、單鏈表節(jié)點的定義。

/*** @param ListHead 待排序列的頭節(jié)點* @param ListEnd 待排序列的尾節(jié)點*/ public static void qsort(Element ListHead, Element ListEnd) {if (ListHead == null || ListEnd == null)return;if (ListHead == ListEnd) {return;}//Slow游標(biāo)，指向序列A的最末尾元素。Element Slow = ListHead;//Fast游標(biāo)，用于遍歷整個待排序列。Element Fast = ListHead.next;//TempEnd游標(biāo)，總是指向Slow游標(biāo)的前驅(qū)節(jié)點，遞歸調(diào)用時需要。Element TempEnd = ListHead;int temp;while (Fast != ListEnd) {//當(dāng)前節(jié)點的值比樞軸小，進(jìn)行交換。if (Fast.data < ListHead.data) {//TempEnd游標(biāo)總是指向Slow的前驅(qū)。TempEnd = Slow;Slow = Slow.next;//交換Slow和Fast游標(biāo)所指的元素的值temp = Slow.data;Slow.data = Fast.data;Fast.data = temp;}Fast = Fast.next;}//交換Slow游標(biāo)所指的元素和樞軸元素的值，使序列成為{A} povit {B}形式temp = ListHead.data;ListHead.data = Slow.data;Slow.data = temp;//遞歸調(diào)用qsort(ListHead, TempEnd);qsort(Slow.next, ListEnd); }

上面的代碼有點問題：

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(head, NULL);

總結(jié)

以上是生活随笔為你收集整理的单链表之快排的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。