排序---快速排序及其切分函数Partition应用
2020-12-13 04:04
标签：代码 while 最大的 左右 函数 quick 数组排序 class 最大 ??快速排序通过一个切分元素将数组分成两个子数组，左子数组小于等于切分元素，右子数组大于切分元素，将这两个子数组排序，也就是将整个数组排序了。 代码如下： ??快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最小的。这种情况下比较次数为Cn=2Cn/2+n，复杂度为O(NlogN)。 ??最坏的情况是，第一次从最大的元素或最小的元素切分，第二次从第二大或者第二小的元素切分，如此这般，最坏情况下的比较次数为N * N /2。为了防止数组一开始就是有序的，我们在选择切分值是，进行随机选取。 ??切分函数partition的应用，荷兰国旗问题，将数组分成三部分，分别对应于小于，等于，大于 切分元素。时间复杂度为O(n)。 排序---快速排序及其切分函数Partition应用 标签：代码 while 最大的 左右 函数 quick 数组排序 class 最大 原文地址：https://www.cnblogs.com/yjxyy/p/11103372.html快速排序
public class Sort{
public static void quickSort(int []arr){
if(arr=null||arr.lengthpublic int[]partition(int []arr,int l,int r){
int less=l-1; //小于区域的右边界
int more=r; //大于区域的左边界，初始包含最右端元素，即切分值。
while(l