java算法递归算法之选择排序

快速排序的原理就是将数组进行分区，分为三个区，然后如果每个区都是有序数组的话，就已经达成了我们的目标

1. 小于基准值的数组组成的子数组
2. 基准值
3. 大于基准值的数组组成的子数组

因此我们需要重复以上的步骤，分别对1和3也选择基准值进行分区，直到数组中最后只剩0个或者1个，那么就达到目标了，重复进行操作即可

那们我们需要写的代码，首先需要先确定一个基准值，然后把大于基准值和小于基准值的给找出来，进行递归调用。

这边我们选择最左边的数组作为基准值，然后使用单指针的方式来标识基准值所在的位置，然后分别与基准值进行比较，小于基准值的，mark+1,然后参数交换，最后将基准值与mark位置的值进行交换即可

这边盗用一下别人的图，看图会更加的清清晰明了

package com.dlh.test.算法;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 递归算法之快速排序 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] string = sc.nextLine().split(" ");
        int[] array = new int[string.length];
        for (int i = 0; i < string.length; i++) {
            array[i] = (Integer.parseInt(string[i]));
        }
        quciksort(array,0,array.length -1);
        for (int num:array){
            System.out.print(num + " ");
        }
    }

    private static void quciksort(int[] array, int low, int high) {
        if(low >= high) {
            return;
        }
        //寻找基准点
        int standardindex = findStandard(array,low,high);
        //分别对基准点的左边和右边进行递归调用
        quciksort(array,low,standardindex-1);
        quciksort(array,standardindex+1,high);
    }

    private static int findStandard(int[] array, int low, int high) {
        //选取最左边的为基准点
        int standard = array[low];
        //mark点先从最左边，开始移动,记录最后基准点所在的位置
        int mark = low;
        for (int i = low+1;i <= high;i++){//从基准点右边开始进行循环比较
            if (array[i] < standard){//如果值小于基准点的话，就要放到基准点的左边去，相当于mark的值要右移，
                mark++;
                int temp = array[i];
                array[i] = array[mark];
                array[mark] = temp;
            }
        }
        //将基准点与mark值的位置进行交换
        array[low] = array[mark];
        array[mark] = standard;
        return mark;
    }
}