单链表的排序----快速排序_单链表快速排序

       谈到排序，我们可以将排序分为：冒泡排序、快速排序、选择排序和快速排序等，这边单链表的排序我采用的是快速排序。

        在给数组排序的时候，我们写过相关的快速排序的代码，关键的点为左指针left，右指针right，新一轮的基准值的定位，以及基准值左右两个子数组的递归（如下图）。但是将这套逻辑套到单链表的排序上是否合适呢？

        由于单链表每个节点包含了一个数据元素和一个指向下个节点的指针，所以可以通过头节点依次遍历来访问后面每一个节点，也可以说头节点确定了一个单链表。但是单链表也存在一个缺点------无法返回上一个节点，所以这样也带来了两个问题：如何递归、新一轮的基准值如何确定。

        那我们该如何解决这个问题呢？我们可以用两个辅助的指针p1和p2，p1用来负责基准值左侧的子链表，p2负责基准值右边的子链表。具体可以看下面的例子：

       

        将start作为第一个节点，并视为基准值，将p1初始化为start指向第一个节点，p2视为一个移动的指针，寻找比基准值小的值。上图p2指向第2个节点，值为9比基准值4大，p2指针向后移动

       

        p2移动到第三个节点值为3，比基准值4小，这个时候就要将p1指针向后移动一个，指向第二个几点，再将第二个节点的值和第三个节点的值交换，最后再将p2指针向后移动、

        p2移动到第四个节点，值为7比基准值3大，p2继续向后移动

        p2指向的值为1，比基准值小，p1向后移动一个节点，并将p1和p2的值交换，此时p2是最后一个节点，循环结束

        

        此时已经过了一轮排序,p1的位置一定在比基准小的值末尾,p2一定在比基准值大的值的末尾，再将基准值和p1节点的值交换，这时我们的链表就分为了两个子链表，在p1节点左侧的链表的值都比基准值小,在p1节点右侧的链表的值都比基准值大，这样就和数组的快排一样了，再对左右两个子链表排序，依次递归即可

        左子链表的start为原始链表的start，end为p1指向的节点

        右子链表的start为p1指向的节点的下一个节点，end为p2指向的节点

完整代码如下：

//交换
void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}
 
//排序
void FastSort(struct Node *start,struct Node *end,bool (*funcPtr)(void*,void *))
{
    if(start == end)
    {
        return;
    }
 
    struct Node *p1 = start;
    struct Node *p2 = p1->next;
 
    //循环终止条件
    while(p2 != end)
    {
        //后面的指针的值比基准值小
        if(funcPtr(p2->data,start->data) == true)
        {
            //p1向后移动,把p1和p2的值交换
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        //交换完后,p2继续向后移动
        p2 = p2->next;
    }
    //最后将基准值和p1交换,p1之前的值都比p1小,p2之后的值都比p2大
    Swap(&start->data,&p1->data);
    //经过一轮排序,p1的位置一定在比基准值小的值末尾,p2一定在比基准值大的值的末尾
    FastSort(start,p1,funcPtr);
    FastSort(p1->next,p2,funcPtr);
}

 注意用到递归时一定要注意终止条件！其中funcPtr为回调函数，目的是为了提高代码的灵活性，可以根据用户所需根据任意条件进行排序。