快速排序

• 这是一篇自学文章,如果有错误地方请及时指出
• 基本思想就是,确定一个在数组中的值,这个值可以将数组分裂为两部分,然后这两部分再分别找到那个中间值,然后再分别按照中间值在切分数组,直到最后不可切分了,也就排序完成了,如下图

• 好了下面将是一次排序的大概流程图

• java代码实现

  public static void main(String[] args) {
    int[] arrs = {7,12,3,5,8,15,9,6,6,6,6,19,-2};
    quickSort(arrs,0,arrs.length - 1);
    System.out.println(Arrays.toString(arrs));
  }
  private static void quickSort(int[] arrs, int l, int r) {
    if (l < r){
        //index就算返回回来的分割点
        int index = getindex(arrs,l,r);
        //有了分割点就知道怎么分割两段数据序列了
        quickSort(arrs,l,index-1);
        quickSort(arrs,index+1,r);
    }
  }
  
  private static int getindex(int[] arrs, int l, int r) {
    int base = arrs[l]; //取第一个值做base值
    //保证不判断过头
    while (l < r){
        //arrs[r] > base 只要比base大的值就继续找,找到比base小的或者相等的
        //就不满足条件就可以确定值的下标了
        while (l < r && arrs[r] >= base){
            //进来就代表比base大
            r --;
        }
        //到这就算找到<=base的值了,然后赋值给left
        arrs[l] = arrs[r];
        //开始寻找比base大的值,流程跟上一个while一样
        while (l < r && arrs[l] <= base){
            l ++;
        }
        //到这就算找到>=base的值了,然后赋值个right
        arrs[r] = arrs[l];
    }
    //然后将base值赋值给right
    arrs[r] = base;
    //返回这个分割点,即right
    return r;
  }