轉自： http://blog.csdn.net/pinkrobin/article/details/5456094

今天在學習《程序員使用算法》時，看到了單鏈表快排序這一節(jié)。初看時感覺程序有很大的問題，但是細細品味之后卻發(fā)現(xiàn)程序設計的極為巧妙，同時又深感自己C語言指針知識之不牢固，特別是指針的指針方面的知識。

單鏈表的快排序和數(shù)組的快排序基本思想相同，同樣是基于劃分，但是又有很大的不同：單鏈表不支持基于下標的訪問。故書中把待排序的鏈表拆分為2個子鏈表。為了簡單起見，選擇鏈表的第一個節(jié)點作為基準，然后進行比較，比基準大節(jié)點的放入左面的子鏈表，比基準大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之后，左面子鏈表的節(jié)點值都小于基準的值，右邊子鏈表的值都大于基準的值，然后把基準插入到鏈表中，并作為連接兩個子鏈表的橋梁。然后根據(jù)左右子鏈表中節(jié)點數(shù)，選擇較小的進行遞歸快速排序，而對數(shù)目較多的則進行跌等待排序，以提高性能。

排序函數(shù)中使用的變量如下：

struct node *right;   //右邊子鏈表的第一個節(jié)點

struct node **left_walk, **right_walk;    //作為指針，把其指向的節(jié)點加入到相應的子鏈表中

struct node *pivot, *old;    //pivot為基準, old為循環(huán)整個待排序鏈表的指針

核心代碼如下：

for (old = (*head)->next; old != end; old = old->next) {

      if (old->data < pivot->data) {  //小于基準,加入到左面的子鏈表,繼續(xù)比較

             ++left_count;

         *left_walk = old;            //把該節(jié)點加入到左邊的鏈表中，

         left_walk = &(old->next);

} else {                      //大于基準,加入到右邊的子鏈表，繼續(xù)比較

         ++right_count;

             *right_walk = old;          

             right_walk = &(old->next);

      }

}

head為struct node **類型，指向鏈表頭部，end指向鏈表尾部，可為NULL，這段程序的重點在于指針的指針的用法，*left_walk為一個指向node節(jié)點的指針，說的明白點*left_walk的值就是node節(jié)點的內(nèi)存地址，其實還有一個地方也有node的地址，那就是指向node的節(jié)點的next域，故我們可以簡單的認為*left_walk = old就是把指向node節(jié)點的節(jié)點的next域改為節(jié)點old的地址，這樣可能造成兩種情況：一種就是*left_walk本來就指向old節(jié)點，這樣就沒有改變?nèi)魏胃淖?，另一種則是改變了*right_walk指向節(jié)點的前一個節(jié)點的next域，使其指向后部的節(jié)點，中間跳過了若干個節(jié)點，不過在這里這樣做并不會造成任何問題，因為鏈表中的節(jié)點要么加入到左面的子鏈表中，要么加入到右面的子鏈表中，不會出現(xiàn)節(jié)點丟失的情況。

下面用圖示說明下上面的問題：

這里假設鏈表的值一次是5、2、4、6、1。根據(jù)程序首先head = left_walk指向值為5的節(jié)點，old指向值為2的節(jié)點，2小于5，所以加入2到左面的子鏈表中，*left_walk=old，我們知道，*left_walk指向的是第一個節(jié)點，這樣做改變了head指針值，使其指向第二個節(jié)點，然后left_walk后移，old后移，4同樣小于5，故繼續(xù)上述操作，但是這是*left_walk和old指向的是同一個節(jié)點，沒有引起任何變化，left_walk和old后移，6大于5，這時不同就出現(xiàn)了，要把其加入到右邊的子鏈表中，故是*right_walk = old，其實right_walk初試化為&right，這句話相當于right = old，即令old當前指向的節(jié)點作為右邊子鏈表的第一個節(jié)點，以后大于基準的節(jié)點都要加入到這個節(jié)點中，且總是加入到尾部。此時right_walk,和old后移，1小于5應該加入到左邊的子鏈表中，*left_walk = old，此時*left_walk指向6，故此語句的作用是更改節(jié)點4的next值，把其改為1的地址，這樣6就從原來的鏈表中脫鉤了，繼續(xù)left_walk和old后移到9節(jié)點，應加入到右邊的子鏈表中，此時*right_walk指向1，故把9節(jié)點加入到6節(jié)點的后面。

這就是基本的排序過程，然而有一個問題需要搞明白，比如有節(jié)點依次為struct node *a, *b, *c，node **p , p = &b，如果此時令*p = c，即實際效果是a->next = c；我們知道這相當于該a的next域的值。而p僅僅是一個指針的指針，它是指向b所指向的節(jié)點的地址的指針，那么當我們更改*p的值的時候怎么會改到了a的next呢(這個可以寫程序驗證下，確實如此)？其實并非如此，我們自習的看看程序，left_walk初始化為head，那么第一次執(zhí)行*left_walk是把head指向了左邊鏈表的起始節(jié)點，然后left_walk被賦值為&(old->next)，這句話就有意思了，我們看以看看下面在執(zhí)行*left_walk=old時的情況，可以簡單的來個等價替換，*left_walk = old也就相當于*&(old->next) = old，即old->nex = old，不過這里的old可不一定是old->next所指向的節(jié)點，應為left_walk和right_walk都指向它們的old節(jié)點，但是卻是不同的。

算法到這里并沒有完，這只是執(zhí)行了一次劃分，把基準放入了正確的位置，還要繼續(xù)，不過下面的就比較簡單了，就是遞歸排序個數(shù)比較小的子鏈表，迭代處理節(jié)點數(shù)目比較大的子鏈表。

整體代碼如下：