快排总结

//交换函数
public static void swap(int arr[],int i,int j)
	{
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
//这个划分函数一次性搞定一片，返回的less+1是区域的起始点，more是区域的终止点；正常情况下more是终止点后一个数
	//但有这么一条语句swap(arr, r, more),这样的话下标more和下标r进行交换了
	//所以现在more是区域的终止点
	//为什么要进行交换呢？因为默认最后一个数字是划分依据，划分依据是不参与划分的，参见牛客-2-45：47
	public static int[] parttion(int arr[],int l,int r)
	{
		int less=l-1;
		int more=r+1;
		int curs=l;
		while(curs<more)
		{
			if(arr[curs]<arr[r])//最后一个数是划分依据
				swap(arr,++less,curs++);
			else if(arr[curs]>arr[r])
				swap(arr, --more, curs);
			else
				curs++;
		}
		swap(arr, r, more);
		int res[]= {less+1,more};
		return res;
	}
//快排
	public static void quicksort(int arr[],int l,int r)
	{
		if(l<r)
		{
			swap(arr, l+(int)(Math.random()*(r-l+1)), r);//随机快排
			int p[]= parttion(arr,l,r);
			quicksort(arr,l,p[0]-1);
			quicksort(arr,p[1]+1,r);
		}
	}

1.快排最差时间复杂度和空间复杂度：
①情况：有序
②时间复杂度：N^2，第一次排倒数第一个位置，第二次排倒数第二个位置，依次类推到排第一个位置。每次进行partition的时间复杂度是N，等价于两个for循环
③空间复杂度：N，第一次partition 返回的数组是倒数第一个，第二次partition 返回的数组是倒数第二个，所以会将所有的数组从头到尾遍历一遍。牛客-基础-2-1：09：43

2.快排最好时间复杂度和空间复杂度：
①情况：每次partition返回的断点都是中点
②时间复杂度：NlogN,按照递归的方法进行求解（见递归时间复杂度博文）,这时log(b,a)=d
③空间复杂度：logN,第一次partition 返回的数组中点，第二次partition 返回的是左边数组的中点，这样就类似于一棵二叉树，类似于二分查找

3.为什么要引入随机快排？
目的就是避免样本是有序数组。随机快排的时间复杂度是logN,在随机快排中，由于选择的点不同，就变成了概率问题。经过期望的推导，结果是NlogN.

4.为什么快排要优于归并排序？
在归并排序的merge操作中，有3个while1个for；在快排中，仅有一个while;在b*T(N/a)相同时，常数项简介的话对应的时间复杂度低。

5.改进的快排为什么优于经典快排
当划分点不唯一时，改进的快排可以将所有的点均找出来。

荷兰国旗问题

//荷兰国旗问题：分成三类，大于、等于、小于
	//牛客-基础-2-25：06，重点理解为什么小于区域curs++,然而大于区域curs不变
	public static int[] netherlandflag(int arr[],int l,int r,int num)
	{
		int less=l-1;
		int more=r+1;
		int curs=l;
		while(curs<more)
		{
			if(arr[curs]<num)//小于num时
				swap(arr,++less,curs++);
			else if(arr[curs]>num)//大于num时，和最后一个互换后，curs是不可以动的，要继续比较
				swap(arr, --more, curs);
			else
				curs++;
		}
		return arr;
	}