快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要笑，然后在按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Partition1：（传统法）
定义一个标准key,此处key选择数组的最后面a[right]，然后定义begin和end，分别从前往后找比key大的和从后往前找比key小的，找到就进行交换，最后将数组变为以key为界的两个数组，进行递归
|
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
|
int Partition1(int *a, int left, int right)
{ assert(a);
int begin = left, end = right - 1, key = a[right];
while (begin < end)
{
//找比key大的
while (a[begin] <= key && begin < end)
{
begin++;
}
//找比key小的
while (a[end] >= key && end > begin)
{
--end;
}
//找到了进行交换
if (begin < end)
{
swap(a[begin], a[end]);
}
}
//将key放在两个数组之间
if (a[begin] > a[right])
{
swap(a[begin], a[right]);
return begin;
}
//只进行left—>right-1的递归
else
{
return right;
}
}void QuickSort1(int *a, int left, int right)
{ assert(a);
if (right > left)
{
int boundary = Partition1(a, left, right);
QuickSort1(a, left, boundary - 1);
QuickSort1(a, boundary + 1, right);
}
} |
Partition2：
依然是在数组中找一个标准key=a[right]，定义prev和cur（初始cur - 1 = prev），分别向前指向比key小的和比key大的，逐次进行交换，直到数组最后面。
|
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
|
int Partition2(int *a, int left, int right)
{ assert(a);
int cur = left, prev = left - 1, key = a[right];
while (cur < right)
{
//a[cur]<key时，prev+1，进行交换
if (a[cur] < key && (++prev) != cur)
{
swap(a[prev], a[cur]);
}
++cur;
}
//最终将数组分成以key为界的两个数组
swap(a[++prev], a[right]);
return prev;
}void QuickSort2(int *a, int left, int right)
{ assert(a);
if (right > left)
{
int boundary = Partition2(a, left, right);
QuickSort2(a, left, boundary - 1);
QuickSort2(a, boundary + 1, right);
}
} |
Partition3：挖坑补位法
定义key=a[right] (任意)，此时a[right]就相当于是一个没有数据的坑，begin（初始）从前往后找比key大的，找到后就将该数据填充到a[right]中，此时begin位置就变成了坑，end从后往前找小的，找到了就填充到上一个坑，最终当begin=end时，将key放进去，数组又变成了以key 为界的两个数组。
|
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
|
int Partition3(int* a, size_t left, size_t right)
{ assert(a);
int begin = left, end = right, key = a[end];
while (begin < end)
{
//begin向前找比key大的
while (begin < end && a[begin] <= key)
{
begin++;
}
//填坑
if (begin < end)
{
a[end] = a[begin];
}
//end从后向前找比key小的
while (end > begin && a[end] >= key)
{
end--;
}
//填坑
if (end > begin)
{
a[begin] = a[end];
}
}
//最终将数组分成以key为界的两个数组
a[begin] = key;
return begin;
}void QuickSort3(int *a, int left, int right)
{ assert(a);
if (right > left)
{
int boundary = Partition3(a, left, right);
QuickSort3(a, left, boundary - 1);
QuickSort3(a, boundary + 1, right);
}
} |
优化法：（三数取中法）
当key为最大最小时，递归次数明显变大（效率低），所以尽量将key设置适中。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int GetMidIndex(int* a, size_t left, size_t right)
{ int mid = left + (right - 1);
if (a[left] < a[right])
{
if (a[mid] < a[left])
return left;
else if (a[mid] < a[right])
return mid;
else
return right;
}
else
{
if (a[mid] < a[right])
return right;
if (a[mid] < a[left])
return left;
else
return mid;
}
} |
非递归实现QuickSort
|
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
|
void QuickSort4(int* a, size_t left, size_t right)
{ assert(a);
stack<int> s;
if (left < right)
{
int boundary = Partition3(a, left, right);
if (left < boundary - 1)
{
s.push(left);
s.push(boundary - 1);
}
if (boundary + 1 < right)
{
s.push(boundary + 1);
s.push(right);
}
while (!s.empty())
{
int end = s.top();
s.pop();
int begin = s.top();
s.pop();
boundary = Partition2(a, begin, end);
if (begin < boundary - 1)
{
//左边界在下，右边界在上。
s.push(begin);
s.push(boundary - 1);
}
if (boundary + 1 < end)
{
s.push(boundary + 1);
s.push(end);
}
}
}
}
|
本文转自 七十七快 51CTO博客，原文链接:http://blog.51cto.com/10324228/1763323