快速排序

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

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

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