冒泡与快速排序

参考资料：
http://blog.csdn.net/morewindows/article/details/6684558
http://ahalei.blog.51cto.com/4767671/1365285

冒泡排序

冒泡排序是一种简单的交换排序
按照从大到小排序一个数组：

每一次，从底到上遍历，比较2个元素，并把较少的元素，逐步的冒上来，经过一轮遍历有，顶上即为最小的元素；
思想一是两两比较，将较小的冒上去

实现代码：

    public static void main(String[] args) {
        int b[] = {1, 5, 9, 3, 2, 0, 4, 7, 6, 8};
        sort3(b);
    }
    
    public static void sort3(int a[]) {
        Utils.print("排序前:\t\t");
        Utils.printArray(a);

        int len = a.length;
        // 外循环
        for (int out = 0; out < len; out++) {
            // 内循环,从后往前查找,不断冒泡
            for (int inner = len - 1; inner > out; inner--) {
                if (a[inner] < a[inner - 1]) {   // 两两比较,并交换
                    int tmp = a[inner];
                    a[inner] = a[inner - 1];
                    a[inner - 1] = tmp;

                    Utils.print(String.format("冒泡数:\t%s\t", tmp));
                    Utils.printArray(a);
                }
            }
        }

        Utils.print("排序后: \t\t");
        Utils.printArray(a);
    }

输出：

Paste_Image.png

优化冒泡排序一，减少比较次数##

如果内循环在某一个循环中，没有发生交换，说明序列已经有序了，直接退出即可；
代码：

public static void main(String[] args) {
        int a[] = {1,5,9,20,0,-3,8,10,56,33,22,30};
        boolean swap = true;
        for (int i = 0; i < a.length - 1; i++) {
            swap = false;    // 每次还原成 false
            for (int j = a.length - 1; j > i; j--) {
                if(a[j] < a[j - 1]) {
                    int tmp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = tmp;
                    swap = true;
                }
            }

            Utils.printArray(a);

            // 没有交换,直接结束,退出循环
            if(!swap) {
                break;
            }
        }
    }

输出：

Paste_Image.png

如果不优化，减少比较次数，输出为：

Paste_Image.png

=====================================================

快速排序

冒泡排序，是相邻的2个数进行比较，并交换传递，有些不合理；

快排，就是来消除这种不太合理的操作；

基本思路

1.从数组中取出一个基准数，base；
2.分区，将数组中，比base小的数，全放入它的左边，比它大或*等于*数，放入其右边；
3.对左右分期，重复1，2操作，直到区间的数，只有一个为止，也就是不断化小分区

实现思路

0. 从初始化数组，取第一个元素，设置为 基数 base；
1. 从数组，最右侧开始，从右往左查找，找到比 base 小的数（类似冒泡）但是不交换，下标记为right;
2. 从左往后查找，找到比base大的数，下标记为 left;
3. 交换 left 与 right 下标数值；
4. right 继续 往左走，left 往右走，重复查找、交换的过程，直到 left = right,
5. 当 left = right 时，交换 基数 与 下标 left 的数值，至此，第一轮 查找交换结束；
6. 分治法，划分区间，在区间内重复 1到5的过程；

** 代码实现 **

    int list[] = {6, 5, 2, 1, 7, 4, 5, 8, 3};

    Utils.print("排序前\t\t");
    Utils.printArray(list);
    quickSort2(list, 0, list.length - 1);
    Utils.print("排序后\t\t");
    Utils.printArray(list);

    private void quickSort2(int a[], int left, int right) {
        // 前置检查
        if (left > right) {
            return;
        }

        // 记录,参数值
        int i, j, baseValue, t;
        baseValue = a[left];
        i = left;
        j = right;

        while (i < j) {
            // 从右往左,查找大于base的数 (下标 j 对应的数)
            while (a[j] >= baseValue && i < j) {
                j--;
            }

            // 从左往右,查找小于base的数 (下标 i 对应的数)
            while (a[i] <= baseValue && i < j) {
                i++;
            }

            // 【交换部分】交换2个数
            if (i < j) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }

        // 【交换部分】基数归位   
        a[left] = a[i];
        a[i] = baseValue;

        System.out.format("base = %d:\t", a[i]);
        printPart(a, left, right);

        // 分治,减小区间
        quickSort2(a, left, i - 1);     // 处理左边的
        quickSort2(a, i+1, right);      // 处理右边的
    }
    
    // 打印序列
    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }
    

输出：

Paste_Image.png