算法：冒泡排序

原理：

每一次整个无序数组进行相邻的进行比较，较大的向后排，这样这次排序的数组中最后的两个数就是有序的，下次不再进行排布最后这个数，这样待排序的数组就少1。直排到最后待排序的数组数量为小于1。

图片展示

这个图片的比较是从后向前进行比较的，不过也是进行多轮比较。

代码实现

public class BubbleSort { public void arrSort(int[] arr,int n){ for(int i =n-1;i>0;i--){ //添加判断标志，当一轮排序中，没有进行交换，说明已经排好，跳出循环 boolean flag = false; for(int j=0;j<i;j++){ if(arr[j]>arr[j+1]){ int sum = arr[j]; arr[j] = arr[j+1]; arr[j+1] = sum; flag = true; } } if(flag==false) break; } } public static void main(String[] args) { int[] arr = new int[]{20,40,30,10,60,50}; new BubbleSort().arrSort(arr,6); System.out.println(Arrays.toString(arr)); } }

时间复杂度

冒泡排序的时间复杂度是O(N²)。有n个数遍历一次的时间复杂度为O(N)，而需要进行n-1轮循环排序，所以是n²。

学习链接