重温算法导论（二） 快速排序

快速排序的思想，就是分而治之的思想，也就是把问题分成两个，再继续分解，到最后。

具体举例的思想如下：算法导论原书的例子：

其实现的伪代码：将一个问题，分解为两个子串的排序问题，利用递归，继续对子串排序，最后实现整串排序

QUICKSORT(A,p,r) //原地重排 p,r 对应下标
	if p < r
		q = PARTITION(A, p, r)
		QUICKSORT(A, p, q-1)
		QUICKSORT(A, q+1, r)
	

关于PARTITION函数的伪代码实现：

PARTITION(A, p, r)
	key = A[r]
	i = p -1
	j = p
	for j to r-1
		if A[j] < key 
			i = i+1
			exchange(A[i], A[j])
	exchange(A[i+1] , A[r])
	return i+1

思想就是取最后一个数作为参考，大的放左边，小的放右边，i表示的是小于参考数的最右边的下标，j是遍历下标

C++代码实现如下：

//快速排序
void exchange(char &x, char &y)
{
	char iTmp;
	iTmp = x;
	x = y;
	y = iTmp;
}

排序函数
int PARTITION(char *pMsg, int p, int r)
{
	int i, j;
	i = p -1 ;
	j = p;
	int iKey = *(pMsg + r);
	for (; j <= r-1; j++)
	{
		if(*(pMsg + j) <= iKey)
		{
			i = i+1;
			exchange(*(pMsg+i), *(pMsg +j));
		}
	}
	exchange(*(pMsg +i + 1), *(pMsg + r));
	return i+1;
}
//递归调用排序函数
void QUICKSORT(char *pMsg, int p, int r)
{
	if(p<r)
	{
		int iq = PARTITION(pMsg, p, r);
		QUICKSORT(pMsg, p, iq -1 );
		QUICKSORT(pMsg, iq + 1, r);
	}
}
int main(int argc, char* argv[])
{
	char szBuf[8] = {2,8,7,1,3,5,6,4};
	QUICKSORT(szBuf, 0, 7);
}