时间复杂度为O(n2)的三种简单排序算法

1.冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

/*** 冒泡排序* 原地排序：是* 稳定排序：是* 空间复杂度：O(1)* 时间复杂度：最好O(n)——最坏O(n^2)——平均O(n^2)[有序度推算]* @param arr*/public static void bubbleSort(int[] arr) {int n = arr.length;if(n<=1) return;for(int i=0;i<n;i++) {boolean flag = false;for(int j=0;j<n-i-1;j++) {if(arr[j]>arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;flag = true;}}if(!flag) break;}System.out.print("[ ");for(int i=0;i<n;i++) {System.out.print(arr[i]+" ");}System.out.println("]");}

2.插入排序

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有⼀个元素，就是数组的第一个元素。插⼊算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插⼊位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

/*** 插入排序* 原地排序：是* 稳定排序：是* 空间复杂度：O(1)* 时间复杂度：时间复杂度：最好O(n)——最坏O(n^2)——平均O(n^2)* @param arr*/public static void insertionSort(int[] arr) {int n = arr.length;//从下标为1的位置开始选择合适的位置插入，因为下标为0的只有一个元素，默认为有序for(int i=1;i<n;i++) {int value = arr[i];//记录要插入的数据int j=i-1;for(;j>=0;j--) {if(arr[j]>value) {arr[j+1] = arr[j];//移动数据}else {break;}}arr[j+1] = value;//保存比较小的数，插入}System.out.print("[ ");for(int i=0;i<n;i++) {System.out.print(arr[i]+" ");}System.out.println("]");}

3.选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

/*** 选择排序* 原地排序：是* 稳定排序：否* 空间复杂度：O(1)* 时间复杂度：时间复杂度：最好O(n^2)——最坏O(n^2)——平均O(n^2)* @param arr*/public static void selectionSort(int arr[]) {int n = arr.length;for(int i=0;i<n;i++) {int value = arr[i];int index = i;for(int j=i+1;j<n;j++) {if(arr[j]<value) {value = arr[j];index = j;}}if(i != index) {int temp = arr[i];arr[i] = arr[index];arr[index] = temp;}}System.out.println("============================");System.out.print("[ ");for(int k=0;k<n;k++) {System.out.print(arr[k]+" ");}System.out.println("]");}