薛映冰的代码狂躁症

人最痛苦的不是失败，而是我本可以

排序算法第二章 快速排序

| Comments

先把快速排序的代码实现贴上来，太晚了，过程改天再加上！！！

快速排序就是把一个数拿出来，然后把小于这个数的扔到一边，把大于它的扔到一边，那这个数就在正确的位置上了,然后把这个数的左边分成一份，右边分成一份，再把这两份进行刚才的做法，一直不停地这样做，直到不能再分。

接下来就要说明怎么把小于它的数扔到一边，大于它的数扔到一边
1、拿出第一个数temp，那第一个数的位置就空了出来
2、从后向前找，找到小于temp的数，记住位置i，把小于temp的数扔到刚才空出来的位置，那 i 的位置又空了出来，
3、从前向后找，找到大于temp的数，记住位置j，把大于temp的数扔到刚才空出来的位置，那 j 的位置又空了出来，
4、重复2，3，直到向前找跟向后找相遇，把temp放在相遇的位置 5、把数组从这个数的位置分成两部分，分别进行1，2，3，4，做完不能再做的时候就停了，^ _ ^

老规矩，附上wiki的地址： http://en.wikipedia.org/wiki/Quicksort 再附上两张排序的图片（来自wiki）：


Quicksort.java 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Quicksort {
    public static void main(String[] args) {
        int[] a = { 3, 5, 2, 6, 1, 8, 9, 45, 23, 87, 34, 65 };
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
        a = new Quicksort().excute(a, 0, a.length - 1);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    public int[] excute(int a[], int left, int right) {
        if (left < right) {
            int temp = a[left], l = left, r = right;
            while (l < r) {
                while (l < r && a[r] > temp)
                    r--;
                if (l < r) {
                    a[l] = a[r];
                    l++;
                }

                while (l < r && a[l] < temp)
                    l++;
                if (l < r) {
                    a[r] = a[l];
                    r--;
                }
            }
            a[l] = temp;
            excute(a, left, l - 1);
            excute(a, r + 1, right);
        }
        return a;
    }
}

Comments