深入單鏈表的快速排序詳解

單鏈表的快排序和數組的快排序基本思想相同，同樣是基於劃分，但是又有很大的不同：單鏈表不支持基於下標的訪問。故書中把待排序的鏈表拆分為2個子鏈表。為了簡單起見，選擇鏈表的第一個節點作為基准，然後進行比較，比基准小得節點放入左面的子鏈表，比基准大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之後，左邊子鏈表的節點值都小於基准的值，右邊子鏈表的值都大於基准的值，然後把基准插入到鏈表中，並作為連接兩個子鏈表的橋梁。然後分別對左、右兩個子鏈表進行遞歸快速排序，以提高性能。
但是，由於單鏈表不能像數組那樣隨機存儲，和數組的快排序相比較，還是有一些需要注意的細節：

1、支點的選取，由於不能隨機訪問第K個元素，因此每次選擇支點時可以取待排序那部分鏈表的頭指針。
2、遍歷量表方式，由於不能從單鏈表的末尾向前遍歷，因此使用兩個指針分別向前向後遍歷的策略實效，
事實上，可以可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。具體方法為：
1)定義兩個指針pslow，pfast，其中pslow指向單鏈表的頭結點，pfast指向單鏈表頭結點的下一個結點;
2)使用pfast遍歷單鏈表，每遇到一個比支點小的元素，就令pslow=pslow->next，然後和pslow進行數據交換。
3、交換數據方式，直接交換鏈表數據指針指向的部分，不必交換鏈表節點本身。
基於上述思想的單鏈表快速排序實現如下：
代碼如下：

/**  
** 單鏈表的快速排序  
** author :liuzhiwei
** date   :2011-08-07  
**/
#include<iostream>
#include<ctime>
using namespace std;
//單鏈表節點
struct SList
{
    int data;
    struct SList* next;
};
void bulid_slist(SList** phead, int n)    //指向指針的指針
{
    int i;
    SList* ptr = *phead;
    for(i = 0; i < n; ++i)
    {
        SList* temp = new SList;
        temp->data = rand() % n;   //產生n個n以內的隨機數
        temp->next = NULL;
        if(ptr == NULL)
        {
            *phead = temp;
            ptr = temp;
        }
        else
        {
            ptr->next = temp;
            ptr = ptr->next;
        }
    }
}
void print_slist(SList* phead)   //輸出鏈表
{
    SList *ptr = phead;
    while(ptr)
    {
        printf("%d ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}
void my_swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void sort_slist(SList* phead, SList* pend)    //將頭指針為phead，尾指針為pend的鏈表進行排序
{
    if(phead == NULL)
        return ;
    if(phead == pend)
        return ;
    SList *pslow = phead;
    SList *pfast = phead->next;
    SList *ptemp = phead;
    while(pfast != pend)
    {
        if(pfast->data < phead->data)        //每次都選擇待排序鏈表的頭結點作為劃分的基准
        {
            ptemp = pslow;          //ptemp始終為pslow的前驅結點
            pslow = pslow->next;
            my_swap(&pslow->data , &pfast->data);       //pslow指針指向比基准小的結點組成的鏈表
        }
        pfast = pfast->next;
    }
    my_swap(&pslow->data , &phead->data);  //此時pslow指針指向比基准小的結點組成的鏈表的最後一個結點，也就是基准的位置，所以要與基准（head結點）交換
    sort_slist(phead , pslow);             //ptemp為左右兩部分分割點（基准）的前一個結點
    sort_slist(pslow->next , NULL);        //右部分是比基准大的結點組成的鏈表
}
void destroy_slist(SList* phead)
{
    SList* ptr = phead;
    while(ptr)
    {
        SList* temp = ptr;
        ptr = ptr->next;
        delete temp;
    }
}
int main(void)
{
    srand(time(NULL));
    printf("Before sort single list\n");
    SList* phead = NULL;
    bulid_slist(&phead, 100);
    print_slist(phead);
    printf("After sort single list\n");
    sort_slist(phead, NULL);
    print_slist(phead);
    destroy_slist(phead);
    system("pause");
    return 0;
}

第二種方法：
選擇鏈表的第一個節點作為基准，然後進行比較，比基准小得節點放入左面的子鏈表，比基准大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之後，左面子鏈表的節點值都小於基准的值，右邊子鏈表的值都大於基准的值，然後把基准插入到鏈表中，並作為連接兩個子鏈表的橋梁。然後根據左、右子鏈表中節點數，選擇較小的進行遞歸快速排序，而對數目較多的則進行迭代排序。
排序函數中使用的變量如下：
代碼如下：

 struct node *right;   //右邊子鏈表的第一個節點
struct node **left_walk, **right_walk;    //作為指針，把其指向的節點加入到相應的子鏈表中
struct node *pivot, *old;    //pivot為基准, old為循環整個待排序鏈表的指針
核心代碼如下：
for (old = (*head)->next; old != end; old = old->next) {
      if (old->data < pivot->data) {  //小於基准,加入到左面的子鏈表,繼續比較
             ++left_count;
         *left_walk = old;            //把該節點加入到左邊的鏈表中，
         left_walk = &(old->next);
} else {                      //大於基准,加入到右邊的子鏈表，繼續比較
         ++right_count;
             *right_walk = old;         
             right_walk = &(old->next);
      }
}

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

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

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

算法到這裡並沒有完，這只是執行了一次劃分，把基准放入了正確的位置，還要繼續，不過下面的就比較簡單了，就是遞歸排序個數比較小的子鏈表，迭代處理節點數目比較大的子鏈表。
完整的代碼如下：
代碼如下：

#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
//鏈表節點  
struct node
{
 int data;  
 struct node *next;  
};  
//鏈表快排序函數
void QListSort(struct node **head,struct node *h);  
//打印鏈表  
void print_list(struct node *head)
{
 struct node *p;  
 for (p = head; p != NULL; p = p->next)
 {  
  printf("%d ", p->data);  
 }  
 printf("\n");  
}  
int main(void)
{
 struct node *head = NULL;  
 struct node *p;  
 int i;  
 /** 
 * 初始化鏈表 
 */
 srand((unsigned)time(NULL));  
 for (i = 1; i < 11; ++i)
 {  
  p = (struct node*)malloc(sizeof(struct node));  
  p->data = rand() % 100 + 1;
  if(head == NULL)
  {
   head = p;
   head->next = NULL;
  }
  else
  {
   p->next = head->next;
   head->next = p;
  }
 }
 print_list(head);
 printf("---------------------------------\n");
 QListSort(&head,NULL);
 print_list(head);
 system("pause");
 return 0;  
}  
void QListSort(struct node **head, struct node *end)
{
 struct node *right;  
 struct node **left_walk, **right_walk;  
 struct node *pivot, *old;  
 int count, left_count, right_count;  
 if (*head == end)
  return;  
 do {  
  pivot = *head;  
  left_walk = head;
  right_walk = &right;  
  left_count = right_count = 0;  
  //取第一個節點作為比較的基准，小於基准的在左面的子鏈表中，  
  //大於基准的在右邊的子鏈表中  
  for (old = (*head)->next; old != end; old = old->next)
  {  
   if (old->data < pivot->data)
   {      //小於基准,加入到左面的子鏈表,繼續比較  
    ++left_count;  
    *left_walk = old;            //把該節點加入到左邊的鏈表中，  
    left_walk = &(old->next);  
   }
   else
   {                         //大於基准,加入到右邊的子鏈表，繼續比較  
    ++right_count;  
    *right_walk = old;             
    right_walk = &(old->next);  
   }  
  }  
  //合並鏈表  
  *right_walk = end;       //結束右鏈表  
  *left_walk = pivot;      //把基准置於正確的位置上  
  pivot->next = right;     //把鏈表合並  
  //對較小的子鏈表進行快排序，較大的子鏈表進行迭代排序。  
  if(left_walk > right_walk)
  {
   QListSort(&(pivot->next), end);  
   end = pivot;  
   count = left_count;  
  }
  else
  {  
   QListSort(head, pivot);  
   head = &(pivot->next);  
   count = right_count;  
  }  
 }
 while (count > 1);   
}