快速排序简介
能点进这篇文章的网友们，我相信对快速排序是有一定了解的，这里不详细介绍快速排序的定义，有想进一步掌握快速排序的实现及原理的可参考这篇文章
快排的递归及非递归实现
下面进入主题，如何对一单链表进行快排呢？我们知道快速排序的核心在于这样一个步骤，即选择某个元素作为基准base，想办法让待排序的序列中所有小于base的元素在左边，所有大于base的元素在右边，之后分别对base的左边和右边重复上述步骤，最终整个序列有序。为此，我们可以想到，如果对单链表也能进行这样的步骤，即选择单链表的某个元素作为base，想办法让整个单链表的元素小于base的在左边，大于base的在右边，之后再对左右两边进行同样步骤，即本文章的主题对单链表进行快速排序。
对单链表使用partition
首先考虑这样一个问题，给定一个单链表的头节点head，节点类型定义如下：
public class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
以及一个int类型的值target，当然不是让你在这个单链表中寻找是否存在这个值，要求是让你原地调整这个单链表，使得单链表中节点值val小于target的在左边，等于的在中间，大于的在右边，可以发现这跟快速排序的核心步骤很类似，能实现这个功能，离快速排序就不远了。下面提供思路：
定义6个Node类型的变量：
Node smallHead = null, smallTail = null;
Node midHead = null, midTail = null;
Node bigHead = null, bigTail = null;
见名知意，很好理解，就不解释了，初始都为null，然后遍历单链表head，小于target的往smallTail后面连接，等于target的往midTail后面连接，大于target的往bigTail后面连接，最后让smallTail连接midHead，midTail连接bigHead，完毕，当然处理过程中需要对为null的情况进行判断，举个例子：
head：2->5->3->8->6->5->1 target=5
遍历过后，
smallHead->smallTail : 2->3->1
midHead->midTail : 5->5
bigHead->bigTail : 8->6
最终head变为：2->3->1->5->5->8->6
代码实现及测试
链表快排代码如下：
public class SingleLinkedList {
public static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public Node quickSort(Node head, Node tail) {
if (head == null || head.next == tail) {
return head;
}
Node smallHead = null, smallTail = null;
Node midHead = null, midTail = null;
Node bigHead = null, bigTail = null;
Node next;
int val = head.val;
while (head != tail) {
next = head.next;
if (head.val < val) {
if (smallHead == null) {
smallHead = smallTail = head;
} else {
smallTail.next = head;
smallTail = head;
}
} else if (head.val == val) {
if (midHead == null) {
midHead = midTail = head;
} else {
midTail.next = head;
midTail = head;
}
} else if (head.val > val) {
if (bigHead == null) {
bigHead = bigTail = head;
} else {
bigTail.next = head;
bigTail = head;
}
}
head.next = null;
head = next;
}
if (smallHead == null) {
smallHead = midHead;
} else {
smallTail.next = midHead;
smallHead = quickSort(smallHead, midHead);
}
if (bigHead == null) {
midTail.next = tail;
} else {
bigHead = quickSort(bigHead, null);
midTail.next = bigHead;
if (bigHead != null && tail != null) {
while (bigHead.next != null) {
bigHead = bigHead.next;
}
bigHead.next = tail;
}
}
return smallHead;
}
}
测试类如下：
import java.util.Arrays;
public class TestSingleLinkedList {
public static final int TIMES = 800000;
public static final int SIZE = 10000;
public static final int MAX = 10000;
public static final int MIN = -10000;
public static int[] array;
public static SingleLinkedList.Node head, cur;
public static void main(String[] args) {
SingleLinkedList sll = new SingleLinkedList();
for (int i = 0; i < TIMES; i++) {
init();
head = sll.quickSort(head, null);
if (!verify()) {
System.out.println(head);
System.out.println("error！");
System.out.println(Arrays.toString(array));
break;
}
}
System.out.println(" All test case successfully pass！Accepted！");
}
public static boolean verify(){
cur = head;
int i;
Arrays.sort(array);
for (i = 0; i < SIZE && cur != null; i++, cur = cur.next) {
if (cur.val != array[i]) {
return false;
}
}
return i == SIZE && cur == null;
}
public static void init(){
int val = (int) (Math.random() * (MAX - MIN) + MIN);
head = new SingleLinkedList.Node(val);
cur = head;
array = new int[SIZE];
array[0] = val;
for (int i = 1; i < SIZE; i++) {
val = (int) (Math.random() * (MAX - MIN) + MIN);
cur.next = new SingleLinkedList.Node(val);
cur = cur.next;
array[i] = val;
}
}
}
笔者经过80万次数的测试，结果都是AC的，验证代码的正确性。
|