【本文鏈接】
http://www.cnblogs.com/hellogiser/p/quick-sort-of-array-and-linked-list.html
【題目】
單鏈表的特點是：單向。設頭結點位head，則最後一個節點的next指向NULL。如果只知道頭結點head，請問怎麼將該鏈表排序？
【分析】
對於數組的快排：有2種方式。
(1)指針相向移動：一個指針i指向頭，一個指針j指向尾，然後兩個指針相向運動並按一定規律交換值，最後找到一個支點p使得支點左邊的值小於支點，支點右邊的值大於支點。由於單鏈表只有next指針，沒有前驅指針，因此這種方法行不通。
(2)指針同向移動：兩個指針i和j，這兩個指針均往數組的右方移動，移動的過程中保持i之前的值都小於選定的key，i和j之間的值都大於選定的key，那麼當j走到末尾的時候便完成了一次支點的尋找。這個思路非常適合單鏈表。
對於數組，我們很容易寫出下面的代碼。
【代碼1】
C++ Code
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
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
// i from left,j from right
// i------------>p<-----------------j
int Partition(int a[], int left, int right)
{
// partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p]
int pivot = a[left], i = left , j = right;
while (i < j)
{
while (a[i] <= pivot) i++;
while (a[j] > pivot) j--;
if (i < j)
myswap(a[i], a[j]);
}
myswap(a[left], a[j]);
return j;
}
void QuickSort(int a[], int left, int right)
{
if(left < right) // less
{
int p = Partition(a, left, right);
QuickSort(a, left, p - 1);
QuickSort(a, p + 1, right);
}
}
void QuickSort(int a[], int n)
{
QuickSort(a, 0, n - 1);
}
【代碼2】
C++ Code
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
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
// i and j both from left
// i,j---------------->
int Partition2(int a[], int left, int right)
{
// partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p]
// left----i<=pivot, i----j>=pivot
int pivot = a[left], i = left , j = left + 1;
while (j <= right)
{
if (a[j] < pivot)
{
i++;
myswap(a[i], a[j]);
}
j++;
}
myswap(a[left], a[i]);
return i;
}
void QuickSort2(int a[], int left, int right)
{
if(left < right) // less
{
int p = Partition2(a, left, right);
QuickSort2(a, left, p - 1);
QuickSort2(a, p + 1, right);
}
}
void QuickSort2(int a[], int n)
{
QuickSort2(a, 0, n - 1);
}
對於鏈表而言，借鑒(2)指針同向移動的思想容易改成如下代碼。
【代碼】
C++ Code
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
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
// i and j both from left
// i,j---------------->
node *Partition2_List(node *left, node *right)
{
// partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p]
// left----i<=pivot, i----j>=pivot
node *pivot = left, *i = left , *j = left->next;
while (j != right)
{
if (j->value < pivot->value)
{
i = i->next;
myswap(i->value, j->value);
}
j = j->next;
}
myswap(left->value, i->value);
return i;
}
void QuickSort2_List(node *left, node *right)
{
if(left != right) // less
{
node *p = Partition2_List(left, right);
QuickSort2_List(left, p);
QuickSort2_List(p->next, right);
}
}
void QuickSort2_List(node *head)
{
QuickSort2_List(head, NULL);
}
【參考】
http://blog.csdn.net/wumuzi520/article/details/8078322
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/quick-sort-of-array-and-linked-list.html
