提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

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

排序 详解 快速 深入 单链
2023-06-13 09:14:59 时间
单链表的快排序和数组的快排序基本思想相同，同样是基于划分，但是又有很大的不同：单链表不支持基于下标的访问。故书中把待排序的链表拆分为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>
usingnamespacestd;
//单链表节点
structSList
{
   intdata;
   structSList*next;
};
voidbulid_slist(SList**phead,intn)   //指向指针的指针
{
   inti;
   SList*ptr=*phead;
   for(i=0;i<n;++i)
   {
      SList*temp=newSList;
      temp->data=rand()%n;  //产生n个n以内的随机数
      temp->next=NULL;
      if(ptr==NULL)
      {
         *phead=temp;
         ptr=temp;
      }
      else
      {
         ptr->next=temp;
         ptr=ptr->next;
      }
   }
}
voidprint_slist(SList*phead)  //输出链表
{
   SList*ptr=phead;
   while(ptr)
   {
      printf("%d",ptr->data);
      ptr=ptr->next;
   }
   printf("\n");
}
voidmy_swap(int*a,int*b)
{
   inttemp;
   temp=*a;
   *a=*b;
   *b=temp;
}
voidsort_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);       //右部分是比基准大的结点组成的链表
}
voiddestroy_slist(SList*phead)
{
   SList*ptr=phead;
   while(ptr)
   {
      SList*temp=ptr;
      ptr=ptr->next;
      deletetemp;
   }
}
intmain(void)
{
   srand(time(NULL));
   printf("Beforesortsinglelist\n");
   SList*phead=NULL;
   bulid_slist(&phead,100);
   print_slist(phead);
   printf("Aftersortsinglelist\n");
   sort_slist(phead,NULL);
   print_slist(phead);
   destroy_slist(phead);
   system("pause");
   return0;
}

第二种方法：
选择链表的第一个节点作为基准，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左面子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后根据左、右子链表中节点数，选择较小的进行递归快速排序，而对数目较多的则进行迭代排序。
排序函数中使用的变量如下：
复制代码代码如下:

 structnode*right;  //右边子链表的第一个节点
structnode**left_walk,**right_walk;   //作为指针，把其指向的节点加入到相应的子链表中
structnode*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为structnode**类型，指向链表头部，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节点的后面。

这就是基本的排序过程，然而有一个问题需要搞明白，比如有节点依次为structnode*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>  
//链表节点  
structnode
{
 intdata;  
 structnode*next;  
};  
//链表快排序函数
voidQListSort(structnode**head,structnode*h);  
//打印链表  
voidprint_list(structnode*head)
{
 structnode*p;  
 for(p=head;p!=NULL;p=p->next)
 {  
  printf("%d",p->data);  
 }  
 printf("\n");  
}  
intmain(void)
{
 structnode*head=NULL;  
 structnode*p;  
 inti;  
 /** 
 *初始化链表 
 */
 srand((unsigned)time(NULL));  
 for(i=1;i<11;++i)
 {  
  p=(structnode*)malloc(sizeof(structnode));  
  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");
 return0;  
}  
voidQListSort(structnode**head,structnode*end)
{
 structnode*right;  
 structnode**left_walk,**right_walk;  
 structnode*pivot,*old;  
 intcount,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);   
}

相关文章