链表的快排

发表于   |   分类于   |  

我们一般都是对数组进行快速排序，如何对链表进行快排呢？
主要的步骤在patition里
主要是用两个指针i和j

  • 如果j.val大于flag，则j往后移
  • 如果j.val小于flag，则swap(j.val,i.next.val)

这样最终小的元素在左边，大的元素在右边
注意这里面交换的i.next的值，因为这里面i指向的元素一直都是小于等于flag的，我们要把大于flag的元素交换到后面.
而且注意，这里的交换都是值交换
例子：
初始状态
1
因为j.val < flag, swap(j.val, i.next.val),因为此时j与i.next相同，其实没有改变
2
此时，j.val > flag,继续
3
此时，j.val > flag,继续
4
因为j.val < flag, swap(j.val, i.next.val),
5
此时j==结尾, swap(begin.val, i.val);
6
一趟快排就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
            quickSort(head, null);
            return head;
        }   
     
    public void quickSort(ListNode pBegin, ListNode pEnd){
        if(pBegin != pEnd){
            ListNode p = partition(pBegin, pEnd);
            quickSort(pBegin, p);
            quickSort(p.next, pEnd);
        }
    }
    
   public ListNode partition(ListNode pBegin, ListNode pEnd){
        int x = pBegin.val;
        ListNode i = pBegin;
        ListNode j = i.next;
        while(j != pEnd){
            if(j.val < x){
                i = i.next;
                int tmp = i.val;
                i.val = j.val;
                j.val = tmp;
            }
            j = j.next;
        }
        int tmp = i.val;
        i.val = pBegin.val;
        pBegin.val = tmp;
        return i;
    }
}

在leetcode上有题要求用nlog(n)的时间复杂度对链表进行排序，用此处的代码会超时，
是因为快速排序采用了递归，容易栈溢出，而且每次我们都采用第一个元素作为flag，这样做并不好，如果采用平均值作为flag，速度会快很多。