Java 快速排序

class Solution {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 8, 1, 7, 2, 6, 3};
        int[] newArr = sort(arr);
        for (int i : newArr) {
            System.out.println(i);
        }
    }


    public static int[] sort(int[] arr) {
        if (arr.length <= 1) return arr;

        int left = 0, right = arr.length - 1, base = arr[0];
        mark:
        while (true) {
            while (true) {
                if (right <= left) break mark;
                if (arr[right] < base) {
                    arr[left] = arr[right];
                    left++;
                    break;
                }
                right--;
            }

            while (true) {
                if (right <= left) break mark;
                if (arr[left] > base) {
                    arr[right] = arr[left];
                    right--;
                    break;
                }
                left++;
            }
        }

        arr[left] = base;

        if (left == 0 || right == arr.length) return arr;
        int[] leftArr = sort(slice(arr, 0, left - 1));
        int[] rightArr = sort(slice(arr, right + 1, arr.length - 1));
        return concate(leftArr, new int[]{base}, rightArr);
    }


    public static int[] slice(int[] arr, int start, int end) {
        int len = end - start + 1;
        int[] ts = new int[len];
        int offset = 0;
        //if(start == end)start--;
        while (offset < len) {
            ts[offset] = arr[offset + start];
            offset++;
        }
        return ts;
    }

    public static int[] concate(int[]... arr) {
        int total = 0;
        int[] result;
        for (int i = 0, len = arr.length; i < len; i++) {
            total += arr[i].length;
        }
        result = new int[total];
        int index = 0;
        for (int i = 0, len = arr.length; i < len; i++) {
            int[] ele = arr[i];
            for (int i1 : ele) {
                result[index++] = i1;
            }
        }
        return result;
    }


}