快排算法Java版-每次以最左边的值为基准值手写QuickSor

如题

手写一份快排算法.
注意, 两边双向找值的时候, 先从最右边起找严格小于基准值的值，再从最左边查找严格大于基准base的值; 并且先右后左的顺序不能反!!这个bug改了好久,233~

https://blog.csdn.net/shujuelin/article/details/82423852
部分内容借鉴了一下上面这篇博客,上面这篇博客还有啊哈算法原书的图解,很直观.
本文的其他作用就只有一个打印数组,实时显示排序效果的优势了;另外可以多测试几次,试着扩大数组范围看看自己写的排序效果~~

QuickSort类和QuickSort算法如下

package com.szs;

import java.util.Random;

/**
 * 以最左边的值为基准值手写QuickSort
 * @param args
 */
public class QuickSort {
    /**
     * 找到基准值，右左交换，分割，递归，结束递归
     * @param array 数组
     * @param left 左边界下标
     * @param right 右边界下标
     */
    public static void quickSort(int array[],int left,int right){
        
        //判断合法
        if(left>right){
            return ;
        }
        
        //确定基准值base, 以最左边的为基准值
        int base = array[left];
        
        //左起的 >基准的值，右起<基准的值
        int l=left,r=right;
        
        while(l<r){
            //先看右边，右起 查找小于基准base的值
            while(array[r]>=base&&l<r)--r;
            //再看左边,找到左起的大于基准base的值
            while(array[l]<=base&&l<r)++l;
             //如果满足条件则交换
            if(l<r){
                int temp=array[l];
                array[l]=array[r];
                array[r]=temp;
            }
        }
        // l==r ,恒为真,可不加此判断
        if(l==r){
             //最后将基准值base为与l和r相等位置的数字交换
             array[left] = array[l];
             array[r] = base;
        }
        
        
        System.out.println("排序中--"+"此次排序范围["+left+","+right+"] "+",基准值base="+base+ " ,l="+l+" "+" ,r="+r);
        print(array);
        
        //左右递归
        quickSort(array, left, l-1);

        quickSort(array, r+1, right);

    }

如下为main方法

    /**
     * main方法,生成10个随机数进行测试
     * @param args
     */
    public static void main(String[] args) {
        
        //生成数组, 
        int array[]=new int[10];    
        for(int i=0;i<array.length;i++){
            array[i] = new Random().nextInt() % 100;
        }
        
        //打印下标
        printIndex(array);
        
        System.out.println("排序前--");
        print(array);
        
        //排序
        quickSort(array, 0, array.length-1);

        System.out.println("quickSort排序后--");
        print(array,l);
    }

如下为print方法

    /**
     * 打印数组,以及判断是否升序
     * @param array
     */
    public static void print(int array[]){
        for(int i=0;i<array.length;i++){
            System.out.print("\t"+array[i]);
        }
        Boolean upOrder=true;
        for(int i=0;i<array.length-1;i++){
            if(array[i]>array[i+1]){
                upOrder=false;
            }
        }
        if(upOrder)System.out.println("\n\t"+"升序");
        else System.out.println("\n\t"+"非升序");
    }    
    /**
     * 打印数组,将每次选取的基准值用[]标出来,以及判断是否升序
     * @param array
     * @param l
     */
    public static void print(int array[],int l){
        for(int i=0;i<array.length;i++){
            if(i!=l)System.out.print("\t"+array[i]);
            else System.out.print("     ["+array[i]+"]");
        }
        Boolean upOrder=true;
        for(int i=0;i<array.length-1;i++){
            if(array[i]>array[i+1]){
                upOrder=false;
            }
        }
        if(upOrder)System.out.println("\n\t"+"升序");
        else System.out.println("\n\t"+"非升序");
    }
    /**
     * 打印数组的下标
     */
    public static void printIndex(int array[]){
        System.out.print("打印下标 ");
        for(int i=0;i<array.length;i++){
            System.out.print("\t "+i);
        }
        System.out.println();
    }
}

执行测试 , 此次数组长度为6

数组长度为6.png

数组长度为10的话,打印出来可能太长了,大家可以自行调整为5或6,这样可以自己进行手算或者调试!

数组长度为10.png