本文共 1307 字，大约阅读时间需要 4 分钟。

public class QuickSort {    private static int[] fillArray() {        Random random = new Random();        int[] array = new int[100];        for (int i = 0; i < array.length; i++) {            array[i] = random.nextInt(10000);        }        return array;    }    public static void main(String args[]) {        int[] array = fillArray();        quickSort(array, 0, array.length - 1);        System.out.println(Arrays.toString(array));    }    private static void quickSort(int[] array, int left, int right) {        if (null == array || left >= right) {            return;        }        int index = getIndex(array, left, right);        quickSort(array, left, index);        quickSort(array, index + 1, right);    }    private static int getIndex(int[] array, int left, int right) {        // 保存基准点        int tmp = array[left];        while (left < right) {            // 从右往左扫描，找到第一个比基准点小的值            while (left < right && array[right] >= tmp) {                right--;            }            array[left] = array[right];            // 从左往右扫描，找到第一个比基准点大的值            while (left < right && array[left] <= tmp) {                left++;            }            array[right] = array[left];        }        // 将基准点放回数组        array[left] = tmp;        return left;    }}

• 时间复杂度：O(nlog(n))
• 空间复杂度：O(log(n))

转载地址：http://ynaii.baihongyu.com/