冒泡排序

冒泡排序的思想就是将相邻的两个位置的数据进行比较,如果前面位置的数据大于后面位置的数据,则将两位置的数据进行交换,未排序元素中最大的数便会像一个气泡一样一路向后冒,最后会将其放在未排序数据的末尾.使其成为已排序数据的首位,时间复杂度O(n^2),空间复杂度O(1) 。

import java.util.Arrays;

public class Test2 {

    public static void main(String[] args) {
        int[] a = {3, 8, 2, 4, 5};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    //冒泡排序：升序
    //1.比较数组中，两个相邻的元素，如果第二个数比第一个数小，我们就交换他们的位置
    //2.每一次比较，都会产生出一个最大，或者最小的数字
    //3.下一轮则可以少一次排序
    //4.依次循环，直到结束
    public static int[] sort(int[] array) {
        //临时变量
        int temp = 0;
        //外层循环，判断我们这个要走多少趟
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;//此为优化，通过flag标识位减少没有意义的比较
            for (int j = 0; j < array.length - 1 - i; j++) {//内层循环，控制每一趟排序多少次
                if (array[j + 1] < array[j]) {//升序降序只有这里不同，降序只需改为>
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag=true;
                }
            }
            if(flag==false){
                break;//此为优化，跳出循环
            }
        }
        return array;
    }
}

分析：
N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。