Java快速排序

逻辑：

数组找一元素作为基准值，比这个值大的放右边，比这个值小的放左边，这个元素就能找到自己正确的位置，而且把数组分成了两块，左边都是比其小的数，右边都是比其大的数。

左右都进行这样的操作，数组就会再次进行分块，每块都是由大小顺序的，当块不能分的时候，数组就拍好了

程序概述：

假设有数组a

1.设置一个基准值，可以设置成数组的第一个元素a[0]

2.设置两个变量（i，j）作为索引的下标（j从后往前索引，i从前往后索引），基准值已经保存了a[0]值，a[0]可以保存j索引到的比基准值小的数，a[j]的数已经被保存了，那么a[j]可以保存i索引到的比基准值大的数，循环反复，直到i=j,那么a[i](或a[j])放基准。

3.a[i]把数组分成两块，这两块看成两个数组，重复（1）（2）过程，直到开始的索引下标大于等于结束的索引下标，说明数组已经分成最小的块（每个小数组中只有一个元素或没有元素），而且每个小数组都是有序的，前面数组所有的数比后面数组的最小值都小或相等，而且小数组都只有一个元素，那么数组就排好序了。

程序编译：

上述（3）重复（1）（2）过程需要方法的递归，下面方法可以进行10次递归

int i=0;
public void a(){
   i++;
   if (i>10) {
       return;
   }
   System.out.println("第"+i+"次递归");
   a();
}

具体的程序：

import java.util.Arrays;

public class Quicksort {

    
    public static void sort(int[] a, int s, int e) {
        if (s >= e) {    
//递归的退出条件，当数组中只有一个或没有元素
            return;
        }
        int i = s;     
//在循环中，下标会不停的动，因此需要一个临时变量来变化
        int j = e;      
//同上
        int num = a[s];        
//每次以数组的第一个元素当基准值
        while (i < j) {       
//ij
            while (num <=a[j] && j > i) j--;  
//只找比基准值小的值，所以是小于等于,j从后往前索引
            a[i] = a[j];        
//a[i]的值在上一轮被保存了，可以赋a[j]值
            while (num >=a[i] && i < j) i++;   
//只找比基准值大的值，所以是大于等于，i从前往后索引
            a[j] = a[i];      
//a[j]的在上面的循环中被保存了，可以放a[i]的值
        }
        a[i] = num;    
//退出循环时i=j，位置找到了，而且a[i]或a[j]的值已经被保存了，可以赋基准值num的值
        sort(a, s, i - 1);  
//基准值左边都是小于基准值的元素作为新的数组，开始递归
        sort(a, i + 1, e);   
//基准值右边都是大于基准值的元素作为新的数组，开始递归
    }
 
//生成随机数组
    public static int[] randomArray(int length) {
        int[] a = new int[length];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random()  * length*10);
        }
        return a;
    }
//测试程序
    public static void main(String[] args) {
        int[] a = randomArray(5);
        System.out.println(Arrays.toString(a));
        sort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
}