快排总结
程序员文章站
2024-03-25 14:34:46
...
//交换函数
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;
}
上一篇: for...in for...of 应用
下一篇: for...in & for...of