深入单链表的快速排序详解

/**  
** 单链表的快速排序  
** 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);
      }
}

#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);   
}