快速排序

快速排序是实践中性能最好的排序是算法，快速排序的时间复杂度跟数据有关，最坏的情况下是O(n^2)，最佳情况为O(n*lg(n))。快速排序类似于合并排序，使用了分治和递归，但是能够做到in place排序。

快速排序首先选定一个中位数，把小于这个数的元素移到左边，大于这个数的元素移到右边，最后把中位数放到中间。这个时候，这个中位数就已经排好序了。然后再对这个中位数左右两侧的子数组递归的执行快速排序，直到所有的“中位数”都排到了合适的位置，整个数组也就排好了。

/** 
 * @brief partition for quick sort
 * 
 * Select the last element as the Q value, elements between index p and i
 * are smaller than Q, elements between index i + 1 and r - 1 are greater than
 * or equal to Q. Swap Q with the elements in index (i + 1). return index of Q.
 *
 * @note Complexity O ( n )
 * @return Index of Q value.
 */
int partition (int *array, int p, int r)
{
	int i, j, x;
	x = array[r];
	i = p - 1;

	for (j = p; j < r; j++)
	{
		if (array[j] < x)
		{
			i++;
			swap (&array[j], &array[i]);
		}
	}

	swap (&array[i + 1], &array[r]);
	return i + 1;
}


/**
 * @brief quick sort
 *
 * Partition array into 2 sub-sequences withe middle number Q index with q,
 * so that in each recursion, Q is placed in the right place.
 * 
 * @note Complexity O ( n*lg(n) )
 */
void quick_sort (int *array, int p, int r)
{
	int q;
	if (p < r)
	{
		q = partition (array, p, r);
		quick_sort (array, p, q - 1);
		quick_sort (array, q + 1, r);
	}
}

这个算法还有两处可以优化的地方：
A）目前算法中每次选择的中位数都是数组的最后一个元素，为了获得更好的平均性能，可以选择一个随机的元素

B）使用循环消除尾递归