乐趣区

关于c:单链表的冒泡快排选择插入归并等多图详解

上节介绍了链表的基本操作 [史上最全单链表的增删改查反转等操作汇总以及 5 种排序算法(C 语言)]()
这节介绍链表的 5 种排序算法。
@[TOC]

0. 稳固排序和原地排序的定义

稳固排序
  假设在待排序的记录序列中,存在多个具备雷同的关键字的记录,若通过排序,这些记录的 绝对秩序放弃不变 ,即在原序列中,ri=rj,且 ri 在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳固的;否则称为不稳固的。像 冒泡排序 插入排序 基数排序 归并排序 等都是稳固排序
原地排序
  基本上 不须要额定辅助的的空间,容许大量额定的辅助变量 进行的排序。就是在原来的排序数组中比拟和替换的排序。像 抉择排序 插入排序 希尔排序 疾速排序 堆排序 等都会有一项比拟且替换操作 (swap(i,j)) 的逻辑在其中,因而他们都是属于原地 (旧址、就地) 排序,而合并排序,计数排序,基数排序等不是原地排序

1. 冒泡排序

根本思维:
  把第一个元素与第二个元素比拟,如果第一个比第二个大,则替换他们的地位。接着持续比拟第二个与第三个元素,如果第二个比第三个大,则替换他们的地位 ….
  咱们对每一对相邻元素作同样的工作,从开始第一对到结尾的最初一对,这样一趟比拟替换下来之后,排在最右的元素就会
是最大的数。除去最右的元素,咱们对残余的元素做同样的工作,如此反复上来,直到排序实现。
具体步骤
  1. 比拟相邻的元素。如果第一个比第二个大,就替换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最初一对。这步做完后,最初的元素会是最大的数。
  3. 针对所有的元素反复以上的步骤,除了最初一个。
  4. 继续每次对越来越少的元素反复下面的步骤,直到没有任何一对数字须要比拟。
工夫复杂度 :O(N2)
空间复杂度 :O(1)
稳固排序 : 是
原地排序: 是


Node *BubbleSort(Node *phead)
{

    Node * p = phead;
    Node * q = phead->next;
    /* 有几个数据就 -1;比方 x 个 i <x-1*/
    for(int i=0;i<5;i++)
    {while((q!=NULL)&&(p!=NULL))
        {if(p->data>q->data)
            {
                /* 头结点和下一节点的替换,要非凡解决,更新新的头 head*/
                if (p == phead)
                {
                    p->next = q->next;
                    q->next = p;
                    head = q;
                    phead = q;
                    /* 这里切记要把 p,q 换回来,失常的话 q 应该在 p 的后面,进行的是 p,q 的比拟
                    * 然而通过指针域替换之后就变成 q,p. 再次进行下一次比拟时,* 就会变成 q,p 的数据域比拟。如果本来 p ->data > q->data, 则进行替换。变成 q ->data 和 p ->data 比拟,* 不会进行替换,所以排序就会谬误。有趣味的能够调试下。*/    
                    Node*temp=p; 
                    p=q;
                    q=temp;        
                }
                /* 解决两头过程,其余数据的替换状况,要寻找前驱节点 if (p != phead)*/
                else 
                {
                    /*p,q 的那个在前,那个在后。指针域的连贯画图好了解一点 */
                    if (p->next == q)
                    {
                        /* 寻找 p 的前驱节点 */
                        Node *ppre = FindPreNode(p);
                        /* 将 p 的下一个指向 q 的下一个 */
                        p->next = q->next;
                        /* 此时 q 为头结点,让 q 的下一个指向 p,连接起来 */
                        q->next = p;
                        /* 将原来 p 的前驱节点指向当初的 q,当初的 q 为头结点 */
                        ppre->next = q;
                        Node*temp=p; 
                        p=q; 
                        q=temp;
                    }
                    else if (q->next == p)
                    {Node *qpre = FindPreNode(q);
                        q->next = p->next;
                        p->next = q;
                        qpre->next = p;
                        Node*temp=p;
                        p=q; 
                        q=temp;
                        }                                    
                }        
            }
            /* 地址挪动 */
            p = p->next;
            q = q->next;
        }
        /* 进行完一轮比拟后,从头开始进行第二轮 */
        p = phead;
        q = phead->next;    
    }
    
    head = phead;
    return head;
}

2. 疾速排序

根本思维
  咱们从数组中抉择一个元素,咱们把这个元素称之为中轴元素吧,而后把数组中所有小于中轴元素的元素放在其右边,
所有大于或等于中轴元素的元素放在其左边,显然,此时中轴元素所处的地位的是有序的。也就是说,咱们无需再挪动中轴
元素的地位。
  从中轴元素那里开始把大的数组切割成两个小的数组 (两个数组都不蕴含中轴元素),接着咱们通过递归的形式,让中轴元素
右边的数组和左边的数组也反复同样的操作,直到数组的大小为 1,此时每个元素都处于有序的地位。
具体步骤
  1. 从数列中挑出一个元素,称为 “ 基准 ”(pivot);
  2. 从新排序数列,所有元素比基准值小的摆放在基准后面,所有元素比基准值大的摆在基准的前面(雷同的数能够到任一边)。在这个分区退出之后,该基准就处于数列的两头地位。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
工夫复杂度 :O(NlogN)
空间复杂度 :O(logN)
稳固排序 :否
原地排序:是


int *QuickSort(Node* pBegin, Node* pEnd)
{if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
        return 0;
 
    // 定义两个指针
    Node* p1 = pBegin;
    Node* p2 = pBegin->next;
    int pivot = pBegin->data;

    // 每次只比拟小的,把小的放在后面。通过一轮比拟后,被分成左右两局部。其中 p1 指向中值处,pbegin 为 pivot。while(p2 != NULL)/* && p2 != pEnd->next */
    {if(p2->data < pivot)
        {
            p1 = p1->next;
            if(p1 != p2)
            {SwapData(&p1->data, &p2->data);
            }
          }
        p2 = p2->next;
   }
   /* 此时 pivot 并不在两头,咱们要把他放到两头,以他为基准,把数据分为左右两边 */
    SwapData(&p1->data, &pBegin->data);
    // 此时 p1 是中值节点
    //if(p1->data >pBegin->data)
    QuickSort(pBegin, p1);
    //if(p1->data < pEnd->data)
    QuickSort(p1->next, pEnd);

}

3. 插入排序

根本思维 : 每一步将一个待排序的记录,插入到后面曾经排好序的有序序列中去,直到插完所有元素为止。
具体步骤
  1. 将待排序序列第一个元素看做一个有序序列,把第二个元素到最初一个元素当成是未排序序列;
  2. 取出下一个元素,在曾经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一地位;
  4. 反复步骤 3,直到找到已排序的元素小于或者等于新元素的地位;
  5. 将新元素插入到该地位后;
  6. 反复步骤 2~5。
工夫复杂度 :O(N2)
空间复杂度 :O(1)
稳固排序 :是
原地排序:是

/* 不好了解能够调试下看下具体过程 */
Node *InsertSort(Node *phead)  
{  
    /* 为原链表剩下用于间接插入排序的节拍板指针 */  
    Node *unsort; 
    /* 长期指针变量:插入节点 */
    Node *t;  
    /* 长期指针变量 */  
    Node *p; 
    /* 长期指针变量 */  
    Node *sort; 
    /* 原链表剩下用于间接插入排序的节点链表:可依据图 12 来了解。*/  
    unsort = phead->next; 
    /* 只含有一个节点的链表的有序链表:可依据图 11 来了解。*/  
    head->next = NULL; 
      /* 遍历剩下无序的链表 */ 
    while (unsort != NULL)  
    {  
        /* 留神:这里 for 语句就是体现间接插入排序思维的中央 */
        /* 无序节点在有序链表中找插入的地位 */  
        /* 跳出 for 循环的条件:*1.sort 为空,此时,sort->data < t->data,p 存下地位,应该放在有序链表的前面
        *2.sort->data > t->data,跳出循环时,t->data 放在有序链表 sort 的后面
        *3.sort 为空 sort->data > t->data,也插入在 sort 后面的地位
        */  
        /* q 为有序链表 */
        for (t = unsort, sort = phead; ((sort != NULL) && (sort->data < t->data)); p = sort, sort = sort->next); 
      
            /* 退出 for 循环,就是找到了插入的地位插入地位要么在后面,要么在前面 */  
        /* 留神:按情理来说,这句话能够放到上面正文了的那个地位也应该对的,然而就是不能。起因:你若了解了下面的第 3 条,就晓得了。*/  
       /* 无序链表中的第一个节点来到,以便它插入到有序链表中。*/
        unsort = unsort->next;    
        /* 插在第一个节点之前 */ 
        /*sort->data > t->data*/
        /*sort 为空 sort->data > t->data*/
        if (sort == phead)  
        {  
            /* 整个无序链表给 phead*/
            phead = t;  
        }  
        /* p 是 sort 的前驱,这样说不太确切,当 sort 到最初时,for 外面有个 sort = sort->next,* 就会把 sort 置空,所以要用 p 暂存上一次 sort 的值。而且执行判断 sort->data < t->data 时,用的也是上一次的 sort
        */
        /*sort 前面插入 */
        /*sort 遍历到了最初,此时,sort->data < t->data,sort 和 p 都为最初一个元素。*/ 
        else  
        {p->next = t;}  
        /*if 解决之后,t 为无序链表,因为要在 phead 前插入。这里先把 t 赋值给 phead,再把 t 的 next 指向 sort,* 就实现了在 sort 之前插入小的元素,很奇妙的一种办法
        *else 解决完之后,sort 寄存的是 sort 的下一次,真正的 sort 寄存在 p 中。不满足条件跳出循环时,判断的是下一次的 sort,然而咱们要用的插入的地位为上一次的 sort,所以要记录下 sort 上一次的地位
        */
        /* 实现插入动作 */
        /* 当 sort 遍历实现为空时,t->next 就是断开前面的元素(sort 为空)*/
        /* 当 sort 不为空时,sort->data > t->data,sort 寄存的元素比 t 要大,放在前面,t->next 就是再链接起来 sort*/
        t->next = sort;   
        /*unsort = unsort->next;*/  
    }  
    head = phead;
    return phead;  
}  

4. 抉择排序

根本思维 :首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素替换地位(如果第一个元素就是最小元素那么它就和本人替换)。其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素替换地位。如此往返,直到将整个数组排序。这种办法咱们称之为抉择排序。
具体步骤
  1. 首先在未排序序列中找到最小(大)元素,寄存到排序序列的起始地位。
  2. 再从残余未排序元素中持续寻找最小(大)元素,而后放到已排序序列的开端。
  3. 反复第二步,直到所有元素均排序结束。
工夫复杂度 :O(N2)
空间复杂度 :O(1)
稳固排序 :否
原地排序:是

Node* SelectSort(Node* phead)                                                
{                                                                                                             
    Node *temp;
    Node *temphead = phead;
    /* 将第一次的最大值设置为头结点 */
    int max = phead->data;
    /* 替换变量 */
     for(int i = 0;i<LengthList(phead);i++)
     {
         /* 每次遍历开始前都要把最大值设置为头结点 */
          max = phead->data;
        while (temphead->next !=NULL)
        {
            /* 寻找最大值 */
            if(max < temphead->next->data)
            {max =  temphead->next->data;}
            /* 挪动指针地位 */
            temphead = temphead->next;
        }    
        /* 找到最大值的地位 */
        temp = FindList(max);
        /* 判断最大值是否和头节点雷同 */
        if(phead != temp)
        {SwapNode(phead,temp);        
        }
        /* 更新下一次遍历的头结点 */
        temphead = temp->next;
        phead = temphead;
     }

} 

  SwapNode 相干代码如下。过后思考只须要了解排序思维就好了,就没有把这个函数的代码放进去。这个代码写的太长太简单了,有工夫我会从新精简下。(说实话,我都快忘了怎么写的了)

/* 替换相邻节点 */
void Swanext(Node *p,Node *q)
{
    
    /* 两头相邻节点 */
    if ((p != head)&&(q != head))
    {
        // /* p 为前一个节点,q 的前驱为 p */
        // /* 寻找 p 的前驱结点 */
        // Node *ppre = FindPreNode(p);
        // Node *temp;
        
        // /* 暂存 p 节点的后继结点,指向 q */
        // temp = p->next;
        // /* 将 q 节点的后继节点赋值给 p 的后继结点,行将 p 节点放到了 q 地位(此时 q 的前驱节点的 next 指针还指向的是 q)*/
        // p->next = q->next;
        // /* 将 p 节点给 q 的 next,行将实现了 q 与 p 的从新连贯 */
        // q->next =p;
        // /* 找到原来 p 的前驱节点,指向 q,即实现了原来 p 的前驱结点和 q 节点的连贯 */
        // ppre->next =q;
            if (p->next == q)
            {Node *ppre = FindPreNode(p);
                p->next = q->next;
                q->next = p;
                ppre->next = q;
                // PrintList(head);

            }
            else if (q->next == p)
            {Node *qpre = FindPreNode(q);
                q->next = p->next;
                p->next = q;
                qpre->next = p;

            }            

    }
    /* 头结点相邻的替换 */    
    else
    {if(p == head)
        {
            p->next = q->next;
            q->next = p;
            head = q;
        }
        else 
        {
            q->next = p->next;
            p->next = q;    
             head = p;        
        }
    }
    

    


}
/* 替换头结点和任意节点(除尾节点外)*/
void SwapHeadAnother(Node *tmphead,Node *p)
{
    /* 寻找 p 的前驱节点 */
    Node *ppre = FindPreNode(p);
    
    Node *temp;
    if(p!=tmphead->next)
    {
        /* 暂存 p 节点 */
        temp = p->next;
        /* 将 tmphead 节点的后继节点赋值给 p 的后继结点,行将 tmphead 节点放到了 p 地位(此时 p 的前驱节点的 next 指针还未断开)*/
        p->next = tmphead->next;
        /* 将 p 的后继结点赋值给 tmphead 的后继结点,同时连贯 p 的前驱和 tmphead*/
        tmphead->next = temp;
        ppre->next =tmphead;
        /* 新的头结点返回给全局 head*/
        head = p;
    }

    else
    {
        /* 头结点和下一节点 */
         tmphead->next = p->next;
         p->next = tmphead;
         head = p;
    }


    

}
/* 替换尾结点和任意节点(除头节点外)*/
void SwapEndAnother(Node *tmpend,Node *p)
{
    /* 寻找 p 的前驱节点 */
    Node *ppre = FindPreNode(p);
    Node *endpre = FindPreNode(tmpend);
    Node *temp;
    if((tmpend==end)&&(p!=tmpend))
    {
        /* 暂存 p 节点 */
        temp = p->next;
        /* 将 tmpend 节点的后继节点赋值给 p 的后继结点,行将 tmpend 节点放到了 p 地位(此时 p 的前驱节点的 next 指针还未断开)*/
        p->next = tmpend->next;
        endpre->next = p;
        /* 将 p 的后继结点赋值给 tmpend 的后继结点,同时连贯 p 的前驱和 tmpend(断开了之前的连贯)*/
        tmpend->next = temp;
        ppre->next =tmpend;
        /* 新的头结点返回给全局 head*/
        end = p;
    }
    else
    {
        p->next = tmpend->next;
        tmpend->next = p;
        end = p;
    }

    

}
/* 替换头结点和尾节点 */
void SwapHeadEnd(Node *tmphead,Node *tmpend)
{
    /* 寻找 tmpend 的前驱节点 */
    Node *endpre = FindPreNode(tmpend);
    Node *temp;
    /* 暂存 tmpend 节点 */
    temp = tmpend->next;
    /* 将 tmphead 节点的后继节点赋值给 tmpend 的后继结点,行将 tmpend 节点放到了 tmphead 地位(此时 tmpend 的前驱节点的 next 指针还未断开)*/
    tmpend->next = tmphead->next;
    /* 将 p 的后继结点赋值给 tmpend 的后继结点,同时连贯 p 的前驱和 tmpend(断开了之前的连贯)*/
    tmphead->next = temp;
    endpre->next =tmphead;
    /* 新的头结点返回给全局 head*/
    head = tmpend;
    end = tmphead;
    // PrintList(tmpend);
}

void SwapRandom(Node *p,Node *q)
{
    /* 除了首尾节点,两头不相邻的两个节点 */
    
    if((p->next != q)||(q->next != p))
    {
        /* 寻找前驱结点 */
        Node *ppre = FindPreNode(p);
        Node *qpre = FindPreNode(q);
        /* 借助一个两头节点传递数据域 */
        Node *temp;
        temp = p->next;
        /* 替换 p 和 q */
        /*2、p 的新后继结点要变成 q 的原后继结点 */
        p->next = q->next;
        /*3、q 的原前趋结点(qpre)的新后继结点要变成 p */
        qpre->next = p;
        /*4、q 的新后继结点要变成 p 的原后继结点(p->next)*/
        q->next = temp;
        /*1、p 的原前趋结点(ppre)的新后继结点要变成 q */
        ppre->next = q;
    }
    /* 两头相邻节点的解决 */
    else if (p->next == q)
    {Node *ppre = FindPreNode(p);
        p->next = q->next;
        q->next = p;
        ppre->next = q;

    }
    else if (q->next == p)
    {Node *qpre = FindPreNode(q);
        q->next = p->next;
        p->next = q;
        qpre->next = p;

    }
    
}

/* 替换任意两个节点 */
void SwapNode(Node*p, Node*q)
{// if(LengthList(head)<2)
    // printf("Can not swap!The Length of list is:%d\r\n",LengthList(head));
    /* 查看是否是头尾节点 */
    /* 对于头尾节点有四种状况
    *1.p 头节点和 q 为两头节点
    *2.p 尾节点和 q 为两头节点
    *3.q 头节点和 p 为两头节点
    *4.q 尾节点和 p 为两头节点
    *5.p 头结点和 q 尾节点
    *6.q 头结点和 p 尾节点
    *7. 其余两头替换的状况
    */
    /*2. 两个节点是否相邻 除去头结点和下一节点相邻的状况,放在 headanother 解决 */
    if((p->next == q)&&(p !=head)&&(q !=head))
    Swanext(p,q);
    else if((q->next == p)&&(p !=head)&&(q !=head))
    Swanext(q,p);
    /*1.p 头节点和 q 为两头节点 */
    else if((p == head)&&(q != end))
    SwapHeadAnother(p,q);
    /*2.p 尾节点和 q 为两头节点 */
    else if ((p == end)&&(q != head))
    SwapEndAnother(p,q);
    /*3.q 头节点和 p 为两头节点 */
    else if((q == head)&&(p != end))
    SwapHeadAnother(q,p);
    /*4.q 尾节点和 p 为两头节点 */
    else if((q == end)&&(p != head))
    SwapEndAnother(q,p);
    /*5.p 头结点和 q 尾节点 */
    else if((p == head)&&(q == end))
    SwapHeadEnd(p,q);
    /*6.q 头结点和 p 尾节点 */
    else if((q == head)&&(p == end))
    SwapHeadEnd(q,p);    
    /*7. 其余两头替换的状况 */
    else 
    SwapRandom(p,q);    
}

5. 归并排序

根本思维 :归并排序是建设在归并操作上的一种无效的排序算法。该算法是采纳分治法(Divide and Conquer)的一个十分典型的利用。
作为一种典型的分而治之思维的算法利用,归并排序的实现由两种办法:
自上而下的递归(所有递归的办法都能够用迭代重写,所以就有了第 2 种办法);
自下而上的迭代;
具体步骤
  1. 申请空间,使其大小为两个曾经排序序列之和,该空间用来寄存合并后的序列;
  2. 设定两个指针,最后地位别离为两个曾经排序序列的起始地位;
  3. 比拟两个指针所指向的元素,抉择绝对小的元素放入到合并空间,并挪动指针到下一地位;
  4. 反复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素间接复制到合并序列尾。
工夫复杂度 :O(NlogN)
空间复杂度 :O(N)
稳固排序 :是
原地排序:否

/* 获取链表两头元素 */
Node *getMiddleNode(Node *pList)
{if (pList == NULL)
    {return NULL;}
    Node *pfast = pList->next;
    Node *pslow = pList;
    while (pfast != NULL)
    {
         pfast = pfast->next;
         if (pfast != NULL)
         {
             pfast = pfast->next;
             pslow = pslow->next;
         }
 
    }
 
    return pslow;
}
 /* 合并有序链表,合并之后升序排列 */
Node *MergeList(Node *p1, Node *p2) 
{if (NULL == p1)
    {return p2;}
    if (NULL == p2)
    {return p1;}
 
    Node *pLinkA = p1;
    Node *pLinkB = p2;
    Node *pTemp = NULL;
    /* 较小的为头结点,pTemp 存下头结点 */
    if (pLinkA->data <= pLinkB->data)
    {
        pTemp = pLinkA;
        pLinkA = pLinkA->next;
    }
    else
    {
        pTemp = pLinkB;
        pLinkB = pLinkB->next;
    }
    /* 初始化头结点,即头结点指向不为空的结点 */
    Node *pHead = pTemp; 
    while (pLinkA && pLinkB)
    {
        /* 合并先放小的元素 */
        if (pLinkA->data <= pLinkB->data)
        {
            pTemp->next = pLinkA;
            /* 保留下上一次节点。如果下一次为 NULL,保留的上一次的节点就是链表最初一个元素 */
            pTemp = pLinkA;
            pLinkA = pLinkA->next;
        }
        else
        {
            pTemp->next = pLinkB;
            pTemp = pLinkB;
            pLinkB = pLinkB->next;
        }
 
    }
    /* 跳出循环时,有一个为空。把不为空的剩下的局部插入链表中 */
    pTemp->next = pLinkA ? pLinkA:pLinkB; 
    head = pHead;
    return pHead;
    
}
Node *MergeSort(Node *pList)
{if (pList == NULL || pList->next == NULL)
    {return pList;}
    /* 获取两头结点 */
    Node *pMiddle = getMiddleNode(pList); 
    /* 链表前半部分,包含两头结点 */
    Node *pBegin = pList; 
    /* 链表后半局部 */
    Node *pEnd = pMiddle->next;
    /* 必须赋值为空 相当于断开操作。pBegin--pMiddle pEnd--- 最初 */
    pMiddle->next = NULL; 
    /* 排序前半部分数据,只有一个元素的时候进行,即有序 */
    pBegin = MergeSort(pBegin); 
    /* 排序后半局部数据 递归了解能够参考 PrintListRecursion;*/
    pEnd = MergeSort(pEnd); 
    /* 合并有序链表 */
    return MergeList(pBegin, pEnd); 
}

  大家的激励是我持续创作的能源,如果感觉写的不错,欢送关注,点赞,珍藏,转发,谢谢!
以上代码均为测试后的代码。如有谬误和不妥的中央,欢送指出。
图片来自网络,侵权请分割我删除

如遇到排版错乱的问题,能够通过以下链接拜访我的 CSDN。

CSDN:CSDN 搜寻“嵌入式与 Linux 那些事”

欢送欢送关注我的公众号:嵌入式与 Linux 那些事,支付秋招口试面试大礼包(华为小米等大厂面经,嵌入式知识点总结,口试题目,简历模版等)和 2000G 学习材料。

退出移动版