1、简介

我相信对于一个数组使用快排是十分简单的，如果对一个无序的单链表排序，是否也能够使用快排呢？
我们先来回顾一下对无序数组的快排：先把数组中的一个元素设置为哨兵（一般是数组的第一个元素），然后利用两个指针指向数组的头和尾。分别移动这两个指针和哨兵进行比较，一趟下来可以把无序数组分为两部分，一部分比哨兵值小，一部分比哨兵值大。哨兵就到了属于它的位置。每一趟快速排序都能确定一个元素的位置。

比如 5 3 1 2 4 6 8 一趟快排下来后就变成了 4 3 1 2 5 6 8。这样5这个位置就固定了。接下来只要对 4 3 1 2 和 6 8 进行快速排序就可以。

2、链表的快排

对于一个单链表来说，无法让指向链表尾的那个结点往前走，只能让指向链表头的那个结点往前走。而快排的核心就在于每一趟排序都能把无序队列分为两部分，一部分比哨兵值小，一部分比哨兵值大。我们可以利用这个思想完成对单链表的快排。

2.1 一趟快排

我们先来完成一趟快速排序。

2.1.1 代码实现

    ListNode* solve(ListNode* head, ListNode* pend){
      	//链表是空或者只有一个元素就返回
        if(!head||head->next==pend) return head;
        int val = head->val; //哨兵值
        ListNode* p = head; //记录“哨兵”的位置
        ListNode* q = p->next; //用于遍历待排序链表的指针
        while(q!=pend){
          	//发现比哨兵结点小的值就交换。从而保证p指针所指的结点比哨兵值小
            if(q->val < val){
                p = p->next;
                swap(p->val, q->val);
            }
            q = q->next;
        }
      	//交换哨兵和p指针指向值，至此哨兵的位置就固定了
        swap(head->val, p->val);
        return p;
    }

2.1.2 代码解析

函数参数包含两个指针，一个指向待排序的链表头，一个指向待排序的链表尾的下一个结点（对于第一趟快排来说，链表尾的下一个结点肯定是null，这样省去了我们去找链表尾的时间）。当然，区别于无序数组的是，我们不会让指向链表尾的那个指针移动，该指针只是作为链表结束的标志。和对无序数组进行快排一样，对单链表进行快排也是需要两个指针的，一个用于遍历（上述代码中的q）。一个用于存放哨兵的位置（上述代码中的p）。整个过程中，p指针左边的值都比哨兵值小，右边的值都比哨兵值大。从而一趟下来，固定了哨兵的位置，并且把待排序序列分为了两个子序列。接下来对这两个子序列递归的排序即可。

2.2 快排

2.2.1 代码实现

    void quick_sort(ListNode* head, ListNode* pend){
        if(head==pend) return;
      	//记录哨兵的位置
        ListNode* p = solve(head, pend);
      	//对子序列进行快排
        quick_sort(head, p);
        quick_sort(p->next, pend);
    }

3、整体代码

	//一趟快排
    ListNode* solve(ListNode* head, ListNode* pend){
        if(!head||head->next==pend) return head;
        int val = head->val;
        ListNode* p = head;
        ListNode* q = p->next;
        while(q!=pend){
            if(q->val < val){
                p = p->next;
                swap(p->val, q->val);
            }
            q = q->next;
        }
        swap(head->val, p->val);
        return p;
    }

    //快排
    void quick_sort(ListNode* head, ListNode* pend){
        if(head==pend) return;
        ListNode* p = solve(head, pend);
        quick_sort(head, p);
        quick_sort(p->next, pend);
    }
	//对指定链表进行快排
    ListNode* sortInList(ListNode* head) {
        quick_sort(head, NULL);
        return head;
    }

单链表的快速排序