## 一、特点

Quicksort's worst-case running time is Θ(n^2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort often the best practical choice for sorting beacuse it is remarkably efficient on the average: its expected running time is Θ(nlgn) and the constant factors hidden in the Θ(nlgn) notation are quite small.

Quicksort is also has the advantage of sorting in place.

## 二、算法

Quicksort, like merge sort, is based on the divide-and-conquer paradigm(分治模式). Three steps:

1. Divide: Partition the array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, in turn less than or equal to each element of A[q+1..r];
2. Conquer: sort the two subarrays A[p..q-1] and A[q+1..r] by recursive calls to quicksort;
3. Combine: Since the subarrays are sorted in place, no needed to combine them: the entire array A[p..r] in now sorted;

## 四、实现

```#define SWAP(a, b) do{int t = a; a = b; b = t;}while(0)

static int partition(int *ary, int begin, int end)
{
int mid_data = ary[end];
int sp = begin;
int p = begin;
for (; p < end; ++p)
{
if (ary[p] < mid_data)
{
SWAP(ary[p], ary[sp]);
sp++;
}
}

SWAP(ary[end], ary[sp]);
return sp;
}

void quicksort(int *ary, int begin, int end)
{
int mid;
if (begin < end)
{
mid = partition(ary, begin, end);
quicksort(ary, begin, mid - 1);
quicksort(ary, mid + 1, end);
}
}
```