时间复杂度O(n2)、空间复杂度O(1)、稳定、原地排序
冒泡排序就是比较与自己相邻的下一个数，如果下一个数比这个大，就交换，否则就进行下一个比较了，经过一轮，大的就会排到最后面去了，循环a.length - 1次即可，注意的是，每次比较只需要比较到倒数第二个，因为最后一个没有下一个与它进行比较了，所以循环a.length-1次
代码如下
import java.util.Arrays;
/**
* @Description: 冒泡排序
* @Author: LinZeLiang
* @Date: 2020-10-04
*/
public class BubbleSort {
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
bubbleSort(a);
System.out.println(Arrays.toString(a));
}
public static void bubbleSort(int[] a) {
//优化冒泡排序，用flag来做标记
boolean flag = true;
//外层循环只会循环length-1次，因为到达最后一个就不用排序了
for (int i = 0; i < a.length - 1 && flag; i++) {
flag = false;
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
//交换两个位置，让大的在右边
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
//只有当有交换的时候才说明无序，falg变成true，接着进行下一次排序，否则说明都已经是有序的，无需再排序了
flag = true;
}
}
}
}
}
时间复杂度O(n2)、空间复杂度O(1)、稳定、原地排序
选择排序，顾名思义就是选择最大（最小）将其与右端（左端）进行交换，如果是本身，则无需交换。如此往复，直到剩下一个，就排序好了。
代码如下
import java.util.Arrays;
/**
* @Description: 选择排序（非稳地排序、原地排序、时间复杂度O(n2)、空间复杂度O(1)）
* @Author: LinZeLiang
* @Date: 2020-10-04
*/
public class SelectSort {
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
selectSort(a);
System.out.println(Arrays.toString(a));
}
public static void selectSort(int[] a) {
//只需要排length-1次即可，最后一个不用排序
for (int i = 0; i < a.length-1; i++) {
//不需要记录最大值，只需要记录角标即可
int pos = 0;
for (int j = 1; j < a.length - i; j++) {
if (a[j] > a[pos]) {
pos = j;
}
}
//如果最后一个就是最大的则无需排序
if (a.length - 1 - i != pos) {
int temp = a[a.length - 1 - i];
a[a.length - 1 - i] = a[pos];
a[pos] = temp;
}
}
}
}
时间复杂度O(n2)、空间复杂度O(1)、不稳定、原地排序
插入排序类似我们在打扑克牌时候，选最左边的为基准，大于他的插入到右边，小于他的插入到左边，慢慢的变有序。即将数字插入到已经有序的数组中适当的位置。插入排序适用于小规模和比较有序的数组排序。
代码如下
import java.util.Arrays;
/**
* @Description: 插入排序
* @Author: LinZeLiang
* @Date: 2020-10-04
*/
public class InsertSort {
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
insertSort(a);
System.out.println(Arrays.toString(a));
}
public static void insertSort(int[] a) {
//因为以第一个为基准，所以第一个不用排序，直接从第二个开始，即角标为1
for (int i = 1; i < a.length; i++) {
//只有比前面的小才进行排序
if (a[i] < a[i - 1]) {
//设置哨兵，先把待排序的值记录下来
int temp = a[i];
int j;
//如果已排序好的数比当前要排序的数大，则需要将该书往后移一位，然后继续比较前一位和待排序的数的大小
//j为i-1即从前一个开始比较，直到比他的值比i的大才插入，否则先后移一位
for (j = i - 1; j >= 0 && a[j] > temp; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
}
}
原文：https://www.cnblogs.com/linzedian/p/13776049.html