기본 빠 른 정렬 과 고급 빠 른 정렬-(재 귀 사용)

void QSort(int * a,int begin,int end)
{
	if(begin < end)
	{
		int i = begin;
		int j = end+1; //  
		int k = a[i],tmp;
		while(i < j) //
		{
			i = i + 1;
			while(a[i] < k)
				i ++;
			j = j - 1;
			while(a[j] > k)
				j --;
			if(i < j)
			{
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
		tmp = a[begin]; //    a[begin]   a[j]   
		a[begin] = a[j];
		a[j] = tmp;
		QSort(a,begin,j - 1);
		QSort(a,j + 1,end);
	}
}

 가장 간단 한 빠 른 정렬 버 전 입 니 다.
 

/*
	    
*/
void insertSort(int * a,int begin,int end)
{
	int tmp;
	for(int j = begin + 1;j<= end;j++)
	{
		tmp = a[j];
		int i = j -1;
		//while(a[i] < a[j]) //     ，  a[i]      ，   a[i]      a[i]
		while(tmp < a[i])
		{
			a[i + 1] = a[i];
			i --;
		}
		a[i + 1] = tmp;
	}
}
/*
	      sgi stl
*/
int middle(int a,int b,int c) 
{
	if(a < b) //            ，  return b ,c a
	{
		if(b < c) // a < b < c
			return b;
		else if(a < c) // a < b ; b > = c ; a < c
			return c;
		else    // a < b ; a >= c 
			return a;
	}
	else {
		if(b > c) // a > b > c
			return b;
		else if(a > c) // a > b ;b <= c;
			return c;
		else             // a > b ; a　< c
			return a;
	}
}
/*
	  ，    k    a[begin],a[middel],a[end]   
	  ，              3，   insertSort
*/
void AdvancedQSort(int * a,int begin,int end)
{
	if(begin >= end)
		return ;
	if(end - begin <= 3)
		insertSort(a,begin,end);
	else
	{
		int i = begin,j = end,k = middle(a[i],a[j],a[(i + i) / 2]),tmp;
	
		while(i < j) //
		{
			i = i + 1;
			while(a[i] < k)
				i ++;
			j = j - 1;
			while(a[j] > k)
				j --;
			if(i < j)
			{
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}

		tmp = a[begin]; //    a[begin]   a[j]   
		a[begin] = a[j];
		a[j] = tmp;
		AdvancedQSort(a,begin,j - 1);
		AdvancedQSort(a,j + 1,end);
	}	
}