🟡前言
21天挑战赛第二天，本文主要讲述有关冒泡排序内容
活动地址：CSDN21天学习挑战赛
🟡概述
冒泡排序是从第一个元素开始比较相邻两个数，并将大的放在后面，直到数据完成从小到大的排序。如下图所示是其原理
🟡两种解题思路及代码实现
1️⃣调用API解决
这种解题思路将会牵扯到三个API
- public static void sort(Comparable[]a)：对数组a中元素进行排序
- public static boolean greater(Comparable x, Cpmparable y)：判断x是否大于y；
一般使用时会这么写：x.compareTo(y) ，再判断值是否 >0 , >0则表示 x>y
- public static void exch(Comparable[]a, int i, int j)：交换数组a中下标为 i 和 j 的元素
解题思路如下
1.想要对数组内元素进行排序，就要调用public static void sort(Comparable[]a)
2.调用循环语句比较元素，比较次数取决于元素个数 j，比较次数 = 元素个数-1 ，即a.length - 1 = i ，每循环一次，次数减去1，直至次数为0
3.要比较的每一对元素是相邻的，从下标为0开始，到最后一个元素，如果下标设为 j，则相邻元素下标值为 j +1，搜索到最后一个元素：j+1<a.length，而 a.length - 1 = i ；所以终止条件是 j < i
4.在循环体内比较相邻两个元素的大小，当前者大于后者时，调换二者次序
5.转换成字符串后打印输出
使用IDEA验证一下程序
具体代码如下
public class BubbleSort { public static void sort(Comparable[] a) { for(int i=a.length-1; i>0; i--){ for(int j=0; j<i; j++){ if(greater(a[j], a[j+1])){ exch(a,j,j+1); } } } } //比较两数大小 private static boolean greater(Comparable x, Comparable y){ return x.compareTo(y) > 0; } //交换数组内两个元素 private static void exch(Comparable[] a, int i, int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
import java.util.Arrays; public class BubbleSortTest { public static void main(String[] args) { Integer[] arr = {4,5,6,3,2,1}; BubbleSort.sort(arr); System.out.println(Arrays.toString(arr)); } }
要注意的是，在写原数组时，要使用Integer来实现Comparable接口
2️⃣普通解法
public class test { public static void main(String[] args) { int arr[] = {4,5,6,3,2,1}; int temp = 0; System.out.println("原数组是"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } for(int i = 0; i <arr.length; i++){ for(int j = i+1; j < arr.length; j++){ if(arr[i] > arr[j]){ temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } System.out.println("\n排序后数组是"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
🟡时间复杂度
比较元素：(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)
交换元素：(n-1) + (n-2) + … + 2 + 1 = 1/2 * (n^2 - n)
总计：n^2 - n
时间复杂度为：O(n^2)
🟡结语
冒泡排序比较容易理解，接下来会介绍选择排序
