本文共 1315 字，大约阅读时间需要 4 分钟。

引子：

快速排序算是归并排序的一个改进吧，思路也是递归二分。

而区别是归并排序使用的中点是随机数列的索引中点，而快速排序使用的中点是一个具体的值，这个值的初始值是随机的，可以定为数组的第1个元素，也可以是第x个。

需要经过一轮切分，来确定这个“中点值”，切分操作还会让让小于中点值的数都放到左边，大于中点的值数都放到右边，所以这一轮切分中会有很多次中点左右两边的交换。

然后再次从左边开始切分成两块，这样不断的递归，递归退出的条件是最左边数索引大于最右边数的索引。

整体逻辑如下：

void QuickSort(int* ua, int nStart, int nEnd){	//递归退出条件	if(nStart >= nEnd)	{		return;	}	int nMid = QuickPartition(ua, nStart, nEnd);	QuickSort(ua, nStart, nMid-1);	QuickSort(ua, nMid+1, nEnd);}

int QuickPartition(int* ua, int nStart, int nEnd){	int i = nStart;	int j = nEnd + 1;	//中点值	int nFlagValue = ua[nStart];	while(1)	{		//找到左边大于中点的值，记录索引		while( ua[++i] < nFlagValue )		{			if( i == nEnd)			{				break;			}		}		//找到右边小于中点的值，记录索引		while( ua[--j] > nFlagValue )		{			if( j == nStart)			{				break;			}		}		//两边向中间靠拢的过程中相遇则退出		if( i >= j)		{			break;		}		//交换两边的值		swap( ua[i], ua[j] );	}	//最后一个从右边换过来的值与中点值交换位置，	//保证中点值的左边都小于中点值，右边都大于中点值	swap( ua[nStart], ua[j] );	//返回将右边最后一个小于中点值的数的索引，做为右边部分的中点值。	return j;}

1，先确定中点值，本算法是取随机数组的第一个数。

2，从第2个数向右遍历，直到找到大于中点值的数，记录索引。

3，从最后一个数向左遍历，直到找到小于中点值的数，记录索引。

4，如果上述两个索引已经相遇或交错，那么退出此过程，否则交换两个值，让大值去右边，小值去左边。

5，直到两个索引相遇或交错。

6，因为第一个值，也就是中间值，是没有参与上面的交换的过程的，所以他是大于右边交换过来的值的，为了保证中间值的左边都小于中间值，需要将此中间值与最后一个从右边换到左边的值的位置交换。

7，返回当前中点值的位置，也就是从第6步中交换得来的值，做为右边部分的中点值。

到此，一轮切分完成，也顺利地将中间值从第一个位置移动到了左右两边临界的位置。

接下来就是递归地重复上面的过程了。

转载地址：http://cmlgb.baihongyu.com/