排序算法-冒泡排序

• 算法思想
• 算法实现
• 算法效率
• • 时间复杂度
  • 空间复杂度

相邻的元素两两比较，较大的数向后(下沉)，较小的数向前(冒起来)，这样一趟比较下来，最大(小)值就会排列在一端
整个过程如同气泡冒起，因此被称作冒泡排序

冒泡排序的步骤是比较固定的

1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个
2. 每趟从第一对相邻元素开始(每次都从index=0开始)，对每一对相邻元素作同样的工作，直到最后一对
3. 针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较，这里要注意的是要知道如何使用变量定义“每次循环后结束后的最后一个元素”

public static void bubblingSort(int[] nums) {
        int endIndex = nums.length - 1;

        while (endIndex > 0) {
            for (int i = 0; i < endIndex; i++) {
                if (nums[i] > nums[i + 1]) {
                    int tmp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = tmp;
                }
            }
            System.out.println(Arrays.toString(nums));
            endIndex--;
        }

    }

最坏时间复杂度为O( N 2 N^2 N2)，这是最坏的情况，因为有可能数组给定的顺序和要排序的顺序截然相反
需要进行N-1趟排序，每趟排序 要进行 N-i(1<=i<=N-1)次 比较

O(1)