1.冒泡排序
冒泡排序是最基本的排序算法，通过对待排序序列从前向后依次比较相邻元素的值，如果发现逆序就进行交换，使值较大的元素从前向后移，就像水底下的气泡一样逐渐向上冒。
冒泡排序算法是重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复进行直到没有再需要交换的元素，这意味着数列已经排序完成。
冒泡排序算法适用于小型数据集，对大型数据集排序性能较差，不建议使用！
冒泡排序算法代码：
private int[] bubbleSort(int arr[]) {
int n=arr.length;
for(int i=0; i<n-1; i++) {
for(int j=0; j<n-i-1; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[jj;
arr[jj = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
①从数组的第一个元素开始，依次比较相邻的两个元素。
②如果前一个元素大于后一个元素，交换它们的位置。
③继续比较下一对相邻元素，直到最后一个元素。
④重复以上步骤，每一轮比较都会将最大的元素"冒泡"到最后面。
⑤当比较结束时，此时数组已经排好序，排序结束。
从代码中可以看出：
①一共进行数组的大小-1次大的循环。
②每一趟排序的次数在逐渐减少。
③如果在某趟排序中，没有发生一次交换，就可以提前结束冒泡排序，这就是优化。
2.冒泡排序的优化
排序过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此可以在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。
private int[] bubbleSort(int arr[]) {
boolean flag=false; //标志是否发生过交换
int n=arr.length;
for(int i=0; i<n-1; i++) {
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) {
return arr; //某次循环没有发生交换，就退出
} else {
flag = false; //重新开始新的循环，重置flag
}
}
return arr;
}
3.冒泡排序的复杂性
时间复杂度分析：在最坏的情况下，冒泡排序需要进行n-1轮比较，每轮比较需要进行n-i次。因此，总的比较次数为(n-1) + (n-2) + … + 2 + 1 = n(n-1)/2，近似为O(n2)。
空间复杂度分析：使用了常数个变量，因此空间复杂度为O(1)。
5.稳定性分析
稳定性指的是相同的数据所在的位置经过排序后是否发生变化。换句话说就是大小相同的两个值在排序之前和排序之后的先后顺序不变，这就是稳定的。
冒泡排序将小的元素往前调或者把大的元素往后调；比较的是相邻的两个元素，交换也发生在这两个元素之间；因为相等的元素不会进行交换，所以稳定。
6.冒泡排序的优点
尽管冒泡排序有点慢，但它也具有某些优点，如下所示：
- 易于实施和理解。
- 由于不需要额外的内存，该算法的空间复杂度为 O（1）。
- 它是一种稳定的排序算法，这意味着具有相同键值的元素在排序输出中保持其相对顺序。