快速排序

  1. 云栖社区>
  2. 博客>
  3. 正文

快速排序

期待l 2018-12-21 13:17:43 浏览9974
展开阅读全文

快速排序

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

quicksort1

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

quicksort

  • 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;
    }

网友评论

登录后评论
0/500
评论
期待l
+ 关注