题目的主要信息:

  • 输入一个无序数组,用冒泡排序对其按从小到大排序

具体做法:

冒泡排序法的基本原理就是比较相邻元素,不断将较大的元素交换到右边。

对于长度为nn的数组,一共排序n1n-1趟,每一趟都比较相邻元素,将较小的交换到前面较大的交换到后面,于是较大的元素沉到最后,较小的元素不断往前冒。而且因为每趟最大的元射会沉到最后,因此每次最大的元素就相当于排好了位置,因此每趟排序长度就会随着趟数减1,不用再排上一趟排好的最末元素。

alt

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
         int[] arr = new int[7];
        for (int i = 0; i < arr.length; i++) { //输入
                    arr[i] = scanner.nextInt();
                }
        scanner.close();
        //冒泡排序
        for(int i = 0; i < arr.length - 1; i++){
         //第i趟比较
            for(int j = 0; j < arr.length - i - 1; j++){
                //开始进行比较,如果arr[j]比arr[j+1]的值大,那就交换位置
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int k = 0;k < arr.length; k++) { //输出
                    System.out.print(arr[k]+" "); 
                 }
        }
}

复杂度分析:

  • 时间复杂度:O(n2)O(n^2)nn为数组长度,冒泡排序两层循环,最坏情况下是逆序,一共比较(n(n1)/2)(n*(n-1)/2)
  • 空间复杂度:O(1)O(1),无额外空间