冒泡排序

  1/**
  2 * 冒泡排序的Java实现
  3 * <p>
  4 * 时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
  5 * </p>
  6 * <b>主要理解思路，实际开发应用基本用不到。</b>
  7 * <p>
  8 * 对于互异数序列，<code>4 5 6 3 2 1</code>，使用冒泡排序对其进行排序应该如何操作？
  9 * <p>
 10 * 冒泡排序的思路：每次冒泡依次比较序列中相邻的元素大小，若前者>后者，则将二者顺序调换。
 11 * 经过一次冒泡，可以保证<b>一个元素在正确的位置上：</b>
 12 * 
 13 * <pre>
 14 *     第一次冒泡的过程：
 15 *       -> 4 5 6 3 2 1
 16 *       -> 4 5 6 3 2 1
 17 *       -> 4 5 3 6 2 1
 18 *       -> 4 5 3 2 6 1
 19 *       -> 4 5 3 2 1 6
 20 *     经过一次冒泡之后，「6」在其正确的位置上了。
 21 * </pre>
 22 * 
 23 * 下面是整个冒泡排序的过程：
 24 * 
 25 * <pre>
 26 *     第一次：4 5 3 2 1 6
 27 *     第二次：4 3 2 1 5 6
 28 *     第三次：3 2 1 4 5 6
 29 *     第四次：2 1 3 4 5 6
 30 *     第五次：1 2 3 4 5 6
 31 *     第六次：1 2 3 4 5 6
 32 * </pre>
 33 * 
 34 * 时间复杂度分析：
 35 * <p>
 36 * 先抛结论：对于N个互异数，通过交换相邻元素进行排序的
 37 * 任何算法（冒泡，插入，选择）时间复杂度都为O(N^2)。
 38 * <p>
 39 * 对于互异数组（不考虑数组内有相同元素的情况）a[N]，
 40 * 若<code>a[i] > a[j](i<j)</code>，称（a[i],a[j]）为a[N]的一个逆序对；
 41 * 反之，若<code>a[i] > a[j](i>j)</code>，称（a[i],a[j]）为a[N]的一个有序对。
 42 * <br>
 43 * 事实上，对互异数排序就是将逆序对通过位置交换变为有序对的过程，
 44 * 因此，有多少逆序对，就需要进行多少次元素交换。
 45 * <br>
 46 * 对于a[N]，最好的情形下，它是完全排序的，那么他的逆序对是0，时间复杂度是O(1);
 47 * <br>
 48 * 最坏的情形，它是完全反序的，那么它的逆序对就是N(N-1)/2 (Cn2)个，时间复杂度是O(N^2);
 49 * <br>
 50 * 简化分析，直接取N(N-1)/4为平均情形的逆序对个数，因此平均复杂度为O(N^2)。
 51 *
 52 * @author wangy
 53 * @version 1.0
 54 * @date 2021/7/2 / 16:07
 55 */
 56public class BubbleSort {
 57    /**
 58     * 复杂度分析：
 59     * 无论在什么情况下，大小为N的数组，都要经过N（N-1）/2 次比较过程，
 60     * 因此此算法的时间复杂度为O(N^2)
 61     * <br>
 62     * 不过，由于数组的容量是固定的，并且比较过程中只使用了2个变量，
 63     * 故此方法的空间复杂度为O(1)
 64     * <br>
 65     * 实际上，这个方法还可以优化，如果已经排序好了，那么就不需要再去比较了。
 66     * 这样可以大大降低复杂度。
 67     *
 68     * @param a 待排序数组
 69     */
 70    static void bubble(int[] a) {
 71        int size = a.length;
 72        for (int i = 0; i < size; i++) {
 73            // 内层循环边界为（size-i-1）
 74            // 因第i次冒泡，应有i个元素已经处于正确的位置，无需再比较
 75            for (int j = 0; j < size - i - 1; j++) {
 76                // swap if f > e
 77                int f = a[j];
 78                int e = a[j + 1];
 79                if (f > e) {
 80                    a[j] = e;
 81                    a[j + 1] = f;
 82                }
 83                System.out.println("\t====>\t" + Arrays.toString(a));
 84            }
 85            System.out.println(Arrays.toString(a));
 86        }
 87    }
 88
 89    // 内层循环如果没有数据交换 --> 已经完全排序，可以跳出冒泡过程。
 90    static void bubble2(int[] a) {
 91        int size = a.length;
 92        for (int i = 0; i < size; i++) {
 93            boolean swaped = false;
 94            // 内层循环边界为（size-i-1）
 95            // 因第i次冒泡，应有i个元素已经处于正确的位置，无需再比较
 96            for (int j = 0; j < size - i - 1; j++) {
 97                // swap if before > after
 98                if (a[j] > a[j + 1]) {
 99                    int tmp = a[j];
100                    a[j] = a[j + 1];
101                    a[j + 1] = tmp;
102                    swaped = true;
103                }
104                System.out.println("\t====>\t" + Arrays.toString(a));
105                if (!swaped)
106                    break;
107            }
108            System.out.println(Arrays.toString(a));
109        }
110    }
111
112    public static void main(String[] args) {
113        // int[] a = new int[]{4, 5, 6, 3, 2, 1};
114        int[] a = new int[] { 1, 2, 3, 4, 5, 6 };
115        BubbleSort.bubble2(a);
116    }
117}