/**

 * 快排

 *

 * @since 2019年2月26日 下午1:37:34

 * @author xuchao

 */

public class QuickSoft {

    public static void quickSoft(int[] data,int start,int end) {

        if(start>=end) {

            return;

        }

        int m = quickSoftPartition(data, start, end);

        quickSoft(data, start, m - 1);

        quickSoft(data, m + 1, end);

    }

    public static int quickSoftPartition(int[] data, int start, int end) {

        int base = data[start];

        int i = start, j = end;

        while (i < j) {

            while (i < j && data[j] >= base) {

                j--;

            }

            while(i<j&& data[i]<=base) {

                i++;

            }

            if(i<j) {

                int t = data[i];

                data[i] = data[j];

                data[j] = t;

            }

        }

        data[start] = data[j];

        data[j] = base;

        return j;

    }

    public static void main(String[] args) {

        int[] data = { 5, 4, 3, 1, 2 };

        quickSoft(data, 0, data.length - 1);

        System.out.println(Arrays.toString(data));

    }

}