快速排序

引子：

快速排序算是歸并排序的一個改進吧，思路也是遞歸二分。

而差別是歸并排序使用的中點是随機數列的索引中點，而快速排序使用的中點是一個具體的值，這個值的初始值是随機的，可以定為數組的第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步中交換得來的值，做為右邊部分的中點值。

到此，一輪切分完成，也順利地将中間值從第一個位置移動到了左右兩邊臨界的位置。

接下來就是遞歸地重複上面的過程了。