冒泡排序

冒泡排序是非常简单的一种排序，我们只需求知道他是怎样交换的就可以了。

基本规则：从左到右依次比较，把最大的数放到右边，依次迭代（先是保证末端排好，再向前迭代）。可以找个“在线算法演示”进行体会。

Java代码

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length-1; i++) {
        for (int j = i; j < nums.length-1; j++) {
            if(nums[j] > nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
}

那还有没有得优化的呢？结果是当然的。当冒泡还没有完成时，已经排好序了。这时，如果还继续冒泡会浪费时间。在这里，我们可以设置一个flag进行状态的记录。

public void bubbleSort2(int[] nums) {
    for (int i = 0; i < nums.length-1; i++) {
        boolean flag = true;
        for (int j = i; j < nums.length-1; j++) {
            if(nums[j] > nums[j+1]) {
                int tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
                flag = false;
            }
        }
        if (flag)
            return;
    }
}

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度

• 给定的数组按照顺序已经排好
  在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

• 给定的数组按照逆序排列
  在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。

• 给定的数组杂乱无章
  在这种情况下，平均时间复杂度是 O(n2)。

由此可见，冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。

END!