|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
/**
* 以p为轴对start-end间的节点进行快排（包括start && 不包括end）；
* 思路：
* 1.将头节点作为轴节点start，从start.next开始遍历，如果节点小于轴start的值，将该节点插入到轴节点后面；
* 2.将轴节点插入合适位置，即找到最后一个小于轴的节点，将该节点与轴节点值互换，此时就链表分为两部分，小于轴节点和大于轴节点；
* 3.递归的遍历2中两部分节点。
*
* @param p
* @param start
* @param end
*/
private
static
void
quickSortWithLinkedList(Node start, Node end) {
if
(start ==
null
|| start == end) {
return
;
}
Node last = start;
Node cur = start.next;
Node next ;
// 1.默认start作为轴，如果index比start小则移动到start的next
while
(cur !=
null
&& cur != end) {
next = cur.next;
if
(cur.value <= start.value) {
if
(start != last) {
//为了防止第一个元素小于轴时发生的重复引用
last.next = next;
Node startNext = start.next;
start.next = cur;
cur.next = startNext;
cur = next;
}
else
{
last = cur;
cur = cur.next;
}
}
else
{
last = cur;
cur = cur.next;
}
}
// 2.将轴移动到合适的位置,与小于轴的节点的值互换
Node newIndex = start.next;
last = start;
// 找到轴插入的位置last，即找到最后一个小于轴的节点；newIndex != end是为了防止将end加入到计算范围中
while
(newIndex !=
null
&& newIndex != end && newIndex.value <= start.value) {
last = newIndex;
newIndex = newIndex.next;
}
//
// 将轴与插入位置上节点的值进行交换
int
temp = last.value;
last.value = start.value;
start.value = temp;
// 3.进行下一次迭代
quickSortWithLinkedList(start, last);
quickSortWithLinkedList(last.next, end);
}
|
本文转自wauoen51CTO博客，原文链接：http://blog.51cto.com/7183397/1967055
，如需转载请自行联系原作者
