🟡前言
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)
🟡结语
冒泡排序比较容易理解,接下来会介绍选择排序