终结快速排序

快速排序作为最常用的排序方式（时间复杂度nlogn），Java内置sort排序用的就是快排，也是面试中常考题型，这里来将这个问题彻底解决，之前总是忘记其中的细节，知其然不知其所以然。

1，首先得接收一个数组

        System.out.println("请输入一个数组(用英文逗号“,”间隔)：");
        String s = sc.nextLine();
        String[] str = s.split(",");
        ArrayList<Integer> list = new ArrayList<>();
            for(int i=0; i<str.length; i++){
            list.add( Integer.parseInt(str[i]));
        }

这里可以用简单数组int[]接收，也可以用ArrayList<integer>接收。使用ArrayList的好处就是方便，不需要设置数组大小，输出显示数组也不需要遍历。

2，正式开始写快排的递归

public static void quickSort(ArrayList<Integer> list, int start, int end){

        //存取开始/结束的数组下标
        int left = start;
        int right = end;

        //设定递归结束条件
        if(left>right || list==null){
            return;
        }
        //选择标志位为数组左边的数
        int flag = list.get(left);
        //注意：不可将条件限定为<=,不然会发生数组越界IndexOutOfBoundsException
        while(left<right){
            //从数组right开始往左找，直到找到一个比标志数小的数退出循环
            //或者当left=right时，退出循环
            while(left<right && list.get(right)>=flag){
                right--;
            }
            //将这个比标志数小的数覆盖在left上
            list.set(left,list.get(right));
            //从数组left开始往右找，直到找到一个比标志数大的数退出循环
            //或者当left=right时，退出循环
            while (left<right && list.get(left)<=flag){
                left++;
            }
            //将这个比标志数大的数覆盖在right上
            list.set(right,list.get(left));
            //最后将标志位赋给left
            list.set(left,flag);

        }
        //递归左右两个数组
        quickSort(list,start,left-1);
        quickSort(list,left+1,end);
    }

注意事项：
1，需要时时判断left<right，一旦相等就得退出循环
2，设定递归结束条件
3，递归数组的左右边界的选定

3，完整代码

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


/*
* 快速排序
* */
public class QuickSort {
    public static void quickSort(ArrayList<Integer> list, int start, int end){

        //存取开始/结束的数组下标
        int left = start;
        int right = end;

        //设定退出递归条件
        if(left>right || list==null){
            return;
        }
        //选择标志位为数组左边的数
        int flag = list.get(left);
        //注意：不可将条件限定为<=,不然会发生数组越界IndexOutOfBoundsException
        while(left<right){
            //从数组right开始往左找，直到找到一个比标志数小的数退出循环
            //或者当left=right时，退出循环
            while(left<right && list.get(right)>=flag){
                right--;
            }
            //将这个比标志数小的数覆盖在left上
            list.set(left,list.get(right));
            //从数组left开始往右找，直到找到一个比标志数大的数退出循环
            //或者当left=right时，退出循环
            while (left<right && list.get(left)<=flag){
                left++;
            }
            //将这个比标志数大的数覆盖在right上
            list.set(right,list.get(left));
            //最后将标志位赋给left
            list.set(left,flag);

        }
        //递归左右两个数组
        quickSort(list,start,left-1);
        quickSort(list,left+1,end);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数组(用英文逗号“,”间隔)：");
        String s = sc.nextLine();
        String[] str = s.split(",");
        ArrayList<Integer> list = new ArrayList<>();
            for(int i=0; i<str.length; i++){
            list.add( Integer.parseInt(str[i]));
        }
        int start = 0;
        int end = list.size()-1;
        quickSort(list, start, end);
        System.out.println(list);
    }
}