Quick Sort采用分治法(Divide and conquer)将一个序列分为两个子序列。
采用快速排序对一个序列S进行排序,主要用到下面的步骤:

1
2
3
4
1. If the number of element in S is 0 or 1, then return.
2. Pick any element *v* in S. This is called the *pivot*.
3. Partition S - {*v*} (the remaining elements in S) into two disjoint groups: S<sub>1</sub> = { *x* \in S - {*v*} \| x <= *v*}, and S<sub>2</sub> = { x \in S - {*v*} \| x >= *v*}.
4. Return {quicksort(S<sub>1</sub>) followed by *v* followed by quicksort(S<sub>2</sub>)}.

递归实现(C语言)

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
void swap(int *x, int *y) 
{
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end)
{
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left) {
quick_sort_recursive(arr, start, left - 1);
}
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len)
{
quick_sort_recursive(arr, 0, len - 1);
}