package xc;

import java.util.Arrays;

import java.util.Random;

/**

 *

 * @author daxin

 *

 * @email leodaxin@163com

 *

 * @date 2017年9月25日 下午6:49:40

 *

 */

public class QuickSort {

    public static void main(String[] args) {

        for (int k = 0; k < 5; k++) {

            int[] nums = new int[10];

            Random rn = new Random();

            for (int i = 0; i < 10; i++) {

                nums[i] = rn.nextInt(1000);

            }

            System.out.println("原来数组：" + Arrays.toString(nums));

            sort(nums, 0, nums.length - 1);

            System.out.println("排序数组：" + Arrays.toString(nums));

        }

    }

    /**

     *

     * @param nums

     *            待排序数组

     * @param start

     *            起始index (0开始)

     * @param end

     *            结束index (0开始计数的结束index)

     */

    public static void sort(int[] nums, int start, int end) {

        if (end - start <= 0) {

            return;

        }

        int mid = partition(nums, start, end);

        sort(nums, start, mid);

        sort(nums, mid + 1, end);

    }

    public static int partition(int[] nums, int start, int end) {

        int key = nums[start];

        while (start < end) {

            while (nums[end] >= key && end > start)

                end--;

            nums[start] = nums[end];

            while (nums[start] <= key && end > start)

                start++;

            nums[end] = nums[start];

        }

        nums[end] = key;

        return end;

    }

}