基础排序算法——冒泡排序

1 算法思想

每一轮，从数组的头部开始，每两个元素比较大小并进行交换。直到这一轮当中最大或者最小的元素被放置在数组的尾部。然后不断的重复这个过程，直到所有元素都排好位置。

2 代码实现

public class BubbleSort {

    public static void main(String[] args) {
        int[] nums = new int[]{9,8,7,6,5,4,3,2,1};
        bubbleSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void bubbleSort(int[] nums) {

        boolean hasChange = true;

        for (int i = 0; i < nums.length - 1 && hasChange; i++) {
            hasChange = false;

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

    // i,j 互换位置
    public static void swap(int[] nums, int indexI, int indexJ) {
        int temp = nums[indexI];
        nums[indexI] = nums[indexJ];
        nums[indexJ] = temp;
    }

}

3 算法分析

空间复杂度：O(1)
因为整个排序过程中，直接在给定的数组里进行元素的两两交换。
时间复杂度：O(n^2)
最好的情况给定的数据已排好，时间复杂度是O(n)。最坏的情况，给定的数组逆序排列，时间复杂度是O(n^2)。
冒泡排序是一种稳定的排序算法