Menu

经典快排和随机快排的区别

2018年5月17日 - 算法,数据结构

经典快排是选择数组中最后一个数字,进行划分,小于等于这个数字的放前面,大于这个数字的放后面,平均时间复杂度为O(nlog2N)但是会出现一种最坏时间复杂度,就是每次选择的最后一个数字都是最坏情况,时间复杂度就会是O(n2)

快排最重要的就是Patation()的位置变换函数,类似荷兰国旗问题

public static int[] partition(int arr[],int left,int right,int num)

{

int index=left;数组左边界

int less=left-1;小于X的区域

int more=right;大于X的区域

while(index<more)

{

if(arr[index]<num)

{

swap(arr,index++,++less);小于X的区域和index做交换,然后小于区域向后扩一位置,index向后扩一位

 

}

else if(arr[index]>num)

{

swap(arr,index,more–);大于X的区域和index做交换,然后大于区域向前扩一位置,注意这时index不++,因为这时index还要和小于区域做比较

}

else

{

index++;

}

}

swap(arr,more,right);

return new int[] {less+1,more};

}

publicstaticvoid swap(int arr[],int i,int j)

{

int t=arr[i];

arr[i]=arr[j];

arr[j]=t;

}

 

详情请参考:https://blog.csdn.net/qq_38238041/article/details/79400144

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: