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

  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: S1 = { x \in S - {v} | x <= v}, and S2 = { x \in S - {v} | x >= v}.
  4. Return {quicksort(S1) followed by v followed by quicksort(S2)}.

递归实现(C语言)

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);
}