quick sort.cpp

经典算法实现

#include "Sort.h"




void Qadjust(int start,int end){

	if (start>=end)
	{
		return ;
	}

	int dist = end -start+1;

	int randx= start+rand()%(dist);


	//第一种实现
	swap(arr[randx],arr[start]);

	int temp= arr[start];

	int i=start-1,j=end+1;
	for (;i<j;){
		
		i++;//如果不先++的话，可能会死循环。arr[i]==arr[j]==temp时
		for (;arr[i]<temp;i++)
			;
		j--;
		for (;arr[j]>temp;j--)
			;
		if (i<j)
		{
			swap(arr[i],arr[j]);
		}
	
		else  {
			Qadjust(start,j);
			Qadjust(j+1,end);
			
			//return i;
		}
	}

//第二种实现
/*	swap(arr[end],arr[randx]);

	int i=start-1,j=start,temp=arr[end];

	for(;j<end;j++){
		
		if (arr[j]<temp)
		{
			i++;
			swap(arr[i],arr[j]);

		} 
		
	}

	swap(arr[end],arr[i+1]);

	Qadjust(start,i);
	Qadjust(i+2,end);
	//return i;*/

	//第三种实现

	/*int i=start-1,j=end+1,k=start+dist/2;
	swap(arr[randx],arr[k]);
	int temp = arr[k];

	for (;i<j;)
	{
		i++;
		for (;arr[i]<temp;i++)
			;
		j--;
		for (;arr[j]>temp;j--)
			;
		if (i<j)
		{
			swap(arr[i],arr[j]);
		}

		else{
			Qadjust(start,j);
			Qadjust(i,end);
		//	return i;
		}
		
		
	}*/
	


}

void  QuickSort(){
	srand( time(0) );

	Qadjust(0,num-1);

	

}