@@ -0,0 +1,2270 @@
+package week3;%0A%0Aimport java.util.Random;%0A%0A/**%0A * Author: Mark%0A * Date  : 2015/3/3%0A * Time  : 22:25%0A */%0Apublic class QuickSort%3CItem extends Comparable%3C? super Item%3E%3E %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        Integer%5B%5D items = new Integer%5B10%5D;%0A        Random random = new Random(System.currentTimeMillis());%0A        for (int i = 0; i %3C 10; i++) %7B%0A            items%5Bi%5D = random.nextInt(100);%0A        %7D%0A        printArray(items);%0A        new QuickSort%3CInteger%3E().sort(items, 0, items.length - 1);%0A        printArray(items);%0A    %7D%0A%0A    private static void printArray(Comparable%5B%5D items) %7B%0A        for (Comparable i : items) %7B%0A            System.out.print(i + %22 %22);%0A        %7D%0A        System.out.println();%0A    %7D%0A%0A    public void sort(Item%5B%5D items, int low, int high) %7B%0A        if (outOfRange(items, low, high)) %7B%0A            throw new IllegalArgumentException();%0A        %7D%0A        if (high %3C= low) return;%0A        int p = partition(items, low, high);%0A        sort(items, low, p - 1);%0A        sort(items, p + 1, high);%0A    %7D%0A%0A    private int partition(Item%5B%5D items, int low, int high) %7B%0A        selectPivot(items, low, high);%0A        Item pivot = items%5Blow%5D;%0A        int i = low, j = high + 1;%0A        while (true) %7B%0A            while (pivot.compareTo(items%5B++i%5D) %3E 0) %7B%0A                if (i == high) break;%0A            %7D%0A            while (pivot.compareTo(items%5B--j%5D) %3C 0) %7B%0A                if (j == low) break;%0A            %7D%0A            if (i %3E= j) break;%0A            swap(items, i, j);%0A        %7D%0A        swap(items, low, j);%0A        return j;%0A    %7D%0A%0A    // %E5%B0%86%E6%9C%80%E4%BD%8E%E4%BD%8D mid %E6%9C%80%E9%AB%98%E4%BD%8D %E4%B8%89%E4%B8%AA%E4%BD%8D%E7%BD%AE%E7%9A%84%E5%85%83%E7%B4%A0%E7%9A%84%E4%B8%AD%E5%80%BC%E6%94%BE%E7%BD%AE%E5%88%B0%E7%AC%AC%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE%0A    private void selectPivot(Item%5B%5D items, int low, int high) %7B%0A        int mid = low + (high - low) / 2;%0A        if (items%5Blow%5D.compareTo(items%5Bmid%5D) %3E 0) %7B%0A            swap(items, low, mid);%0A        %7D%0A        if (items%5Bmid%5D.compareTo(items%5Bhigh%5D) %3E 0) %7B%0A            swap(items, mid, high);%0A        %7D%0A        if (items%5Blow%5D.compareTo(items%5Bmid%5D) %3C 0) %7B%0A            swap(items, low, mid);%0A        %7D%0A    %7D%0A%0A    private boolean outOfRange(Item%5B%5D items, int low, int high) %7B%0A        return low %3C 0 %7C%7C high %3E= items.length;%0A    %7D%0A%0A    private void swap(Item%5B%5D items, int i, int j) %7B%0A        Item tmp = items%5Bi%5D;%0A        items%5Bi%5D = items%5Bj%5D;%0A        items%5Bj%5D = tmp;%0A    %7D%0A%0A%7D%0A

add quicksort