冒泡排序

冒泡排序可以说是最简单的一种排序算法，它通过不断比较相邻的两个元素，如果顺序不符就交换它们，遍历到尽头会确定一个元素的最终位置。过程就像冒泡，因而得冒泡此名。

动画演示

由动画可以看出，从头开始遍历数组，相邻元素两两比较，如果顺序不对就交换，直到尽头(黄色部分是已确定位置的元素),确定一个元素的位置，右边界向前移动一位。

算法描述

• 两个循环，外循环指定遍历的右边界，内循环遍历数组并做冒泡处理。
• 内循环每遍历完一次，则一个元素确定其最终位置(即右边界)，然后右边界前移，继续重复以上操作。

代码

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

分析

排序算法	时间复杂度 (平均)	时间复杂度 (最坏)	时间复杂度 (最好)	空间复杂度	稳定性
冒泡排序					稳定

相邻两个数相同时不交换位置，所以稳定。
最好时间复杂度对代码是有要求的，以下为改进代码

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sort(int[] nums) {
        boolean didSwap = false;
        for(int i = nums.length - 1;i >= 0;i--){
            didSwap = false;
            for(int j = 0;j < i;j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j, j+1);
                    didSwap = true;
                }
            }
            if(!didSwap) return;
        }
    }

当本轮内循环没有做过元素交换，说明数组本身是有序的，则只对数组进行了一次遍历直接就返回了。