荷蘭國旗快排

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>


using namespace std;
/*  
荷蘭國旗快排
*/
class Sort
{
public:
	int* Partition(int arr[], int L, int R)
	{
		int less = L - 1;
		int more = R;
		int cur = L;
		while(cur < R)
		{
			if(arr[cur] < arr[R])
				swap(arr[cur++], arr[++less]);
			else if(arr[cur] > arr[more]) 
				swap(arr[cur], arr[more--]);
			else
				cur++;
		}
		swap(arr[less+1], arr[R]);
		int* arrN = new int[2];
		arrN[0] = less+1;
		arrN[1] = more;
		return arrN;
	}

	void QuickSort(int arr[], int L, int R)
	{

		if(arr != NULL && L < R)
		{
			int * arrP = Partition(arr, L, R);
			QuickSort(arr, L, arrP[0] - 1);
			QuickSort(arr, arrP[1] + 1, R);
		}
	}
	
};


int _tmain(int argc, _TCHAR* argv[])
{
	Sort s;

	int arr[] = {1,5,7,9,6};

	for(int i=0; i<5;i++)
	cout << arr[i] << endl;
	cout << endl;
	s.QuickSort(arr, 0, 4);
	for(int i=0; i<5;i++)
	cout << arr[i] << endl;
	system("PAUSE");
    return 0;
}