/**
 * 快排
 * <p>
 * Created by Avalon on 2017/1/21.
 */
public class QuickSort {

    public static void quickSort(int[] arrs) {
        process(arrs, 0, arrs.length - 1);
    }

    private static void process(int[] arrs, int start, int end) {
        if (start < end) {
            int t = quickSortProcess(arrs, start, end, start);
            process(arrs, start, t - 1);
            process(arrs, t + 1, end);
        }
    }

    private static int quickSortProcess(int[] arrs, int start, int end, int targetIdx) {
        boolean right = true;

        int i = start, j = end;

        int t = targetIdx;
        int tv = arrs[targetIdx];
        while (i <= j) {
            if (right) {
                if (arrs[j] < tv) {
                    arrs[t] = arrs[j];
                    t = j;
                    right = false;
                }
                j--;
            }

            if (!right) {
                if (arrs[i] > tv) {
                    arrs[t] = arrs[i];
                    t = i;
                    right = true;
                }
                i++;
            }
        }

        arrs[t] = tv;
        return t;
    }
}