交换排序-冒泡排序

• 时间复杂度：高效的排序算法，比较次数和移动次数都应该尽可能的少。
• 空间复杂度：算法执行期所需要辅助空间和待排序的数据量无关。理想空间复杂度为O(1)

简述

冒泡排序就如同水中的水泡往水面上浮过程一样，越来越大。冒泡排序是最简单的交换排序，通过两两相邻比较，如果发生逆序则进行交换，如此循环，直至全部排序成功

算法思想

1. 设定排序数组为r[0··n-1]中，一共n个待排序数。第一躺排序：首先将r[0]与r[1]进行比较，若逆序，则交换r[0]与r[1]，然后将r[1]与r[2]进行比较，逆序则交换，一次类推，直到r[n-2]与r[n-1]比较判断后，第一趟排序结束，最后一个数字则最终排序的最后一位值。
2. 第二趟排序，则是将r[0]到r[n-1]，第一步方法进行排序，得到最终排序的r[n-2]位值。
3. 重复上述比较过程，知道某一趟，没有进行交换为止，说明已经排序结束。

算法实现

public void sort() {
        //待排序数组
        int[] ints = new int[]{1, 33, 44, 55, 6, 2, 3, 22, 77, 88, 123, 54};

        //从小到大
        //最大比较n-1趟
        for (int i = 1; i <= ints.length; i++) {
            System.out.println("第" + i + "趟排序");
            boolean hasChange = false;
            //每一趟比较0到j
            for (int j = 0; j < ints.length - i; j++) {
                if (ints[j] >= ints[j + 1]) {
                    int temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                    hasChange = true;
                }
            }

            if (!hasChange) {
                System.out.println("没有交换，排序完成");
                break;
            }
        }

        for (int intTemp : ints) {
            System.out.print(intTemp + " ");
        }
    }

算法实现一般是两重循环，外层是控制躺数，内层控制比较数。具体如何控制可根据自己的想法去实现。

算法分析

• 时间复杂度
  • 最好的情况：初始的时候就排序好了，只需要进行一趟比较，且不移动记录
  • 最坏的情况：需要进行n-1趟排序，那么总的关键字比较次数：第一趟n-1次，第二趟n-2次，第三趟n-3次，所以总的为n(n-1)/2约等于n²/2。总的移动次数(假定每次交换都移动3次记录)，3n(n-1)/2约等于3n²/2。

所以，最好和最坏平均一下，那么平均情况下，冒泡排序记录移动次数为n²/4和3n²/4。时间复杂度为O(n²)

• 空间复杂度
  • 由于交换的时候，辅助空间只需要一个来做暂时存储，所以空间复杂度为O(1)

算法特点

• 是稳定排序
• 由于是相邻比较，所以可用于链式存储结构
• 移动次数比较多，算法平均性能比直接插入排序差。当初始记录无序，n较大的时候不适用了

冒泡可以说是最基本的排序手法之一。这个手法想必是各种语言学习的时候都有所使用的，对咱们排序思想有启发作用。