快速排序

快排
partition
给一个数组 一个数字 :小于的放左边 大于的放右边
时间复杂度 O(n) 空间复杂度 O(1)

遍历

• 当前数字 <= 划分值 , 当前数字和小于等于 区域的下一个数字交换, <=区扩容,当前数字跳下一个位置
• ---- > 划分值, 直接下一个
  实质的过程就是小于等于区域 推着 当前数走 中间留下了大于等于区域

拓展 partition
< = > 区
方法法
一个小于区域 一个大于区域 遍历

• == 当前数直接跳下一个
• <划分值 小于区扩 当前数跳下一个
• --->当前数和大于区的上一个交换 大于区扩 当前数不变 因为换过来的这个数 没有看过 而小于区来说 已经看过了
• 当前数和大于区撞上 停 ! 结束整个过程
  荷兰国旗问题

static int [] b partition(int [] a,int l, int r,int p){
   int less=l-1;
   int more=r+1;
   while(l < more){//等于more 的时候就不用循环了 
        if(a[l]<p){
        swap (a,++less,l++);
        }else if(a[l]>p){
        swap(a,++more,l);
        }else{
          l++;
        }
   }
   return new int [] {less+1,more-1};
}

static void swap(int [] a,int i,int j){
    int tem=a[i];
    a[i]=a[j];
    a[j]=a[tem];
}

快排 拿最后一个数 做目标 在排完之后拿最后一个数和 >区的后一个数做交换

• 一次搞定一个数 然后递归 左边和右边
• basecase 就是只有一个数了之后
• 改进成荷兰国旗问题之后 一次就能搞定一片的等于区域 而不是一个数

最差情况
123456
每次partition 都只搞定一个数 n^2
情况要好的话 就是要划分值 打到中间位置
T(n)=2T(n)+O(n)------n*logn

改进 随机选一个数作为划分

public class quicksort {
    static int[] partition(int[] a, int l, int r) {
        int less = l - 1;//小于区域
        int more = r;//大于区域
        while (l < more) {   //l在变化 像一个指针  more 是大于区域
            if (a[l] < a[r]) {//最后一个数是标准
                swap(a, ++less, l++);
            } else if (a[l] > a[r]) {
                swap(a, --more, l);
            } else {
                l++;
            }
        }
        swap(a, more, r);//交换了最后一个数到大于区域的第一个
        return new int[]{less + 1, more}; //返回交换之后的等于的数组范围;
    }

    static void quicksort(int[] a) {
        if (a == null && a.length < 2) {
            return;
        }
        quicksort(a, 0, a.length - 1);
    }

    static void quicksort(int[] a, int l, int r) {
        if (l < r) {
            int[] ret = partition(a, l, r);
            quicksort(a, 0, ret[0] - 1);
            quicksort(a, ret[1] + 1, r);
        }
    }

    static void swap(int[] a, int i, int j) {
        int tem = a[i];
        a[i] = a[j];
        a[j] = tem;
    }
}

image.png