冒泡排序
算法步骤
1、比较相邻的元素，如果第一个比第二个大，就交换它们两个；
2、对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
3、针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；
4、重复步骤1~3，直到排序完成。
代码实现
package com.example.helloworld;
import java.util.Arrays;
public class BubbleSort {
public static void bubblesort(int[] arr){
int len = arr.length;
for (int i = 0; i < len-1; i++){
boolean flag = true;
for (int j = 0; j < len-i-1; j++){
if (arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
System.out.println("第" + (i + 1) + "轮排序结果：" + Arrays.toString(arr));
if (flag){
break;
}
}
}
public static void main(String args[]){
int[] array_1 = {2,5,6,7,8,1,9};
int[] array_2 = {23,12,67,45,99,17,13};
System.out.println("array_1冒泡排序结果为：");
BubbleSort.bubblesort(array_1);
System.out.println("array_2冒泡排序结果为：");
BubbleSort.bubblesort(array_2);
}
}
array_1冒泡排序结果为：
第1轮排序结果：[2, 5, 6, 7, 1, 8, 9]
第2轮排序结果：[2, 5, 6, 1, 7, 8, 9]
第3轮排序结果：[2, 5, 1, 6, 7, 8, 9]
第4轮排序结果：[2, 1, 5, 6, 7, 8, 9]
第5轮排序结果：[1, 2, 5, 6, 7, 8, 9]
第6轮排序结果：[1, 2, 5, 6, 7, 8, 9]
array_2冒泡排序结果为：
第1轮排序结果：[12, 23, 45, 67, 17, 13, 99]
第2轮排序结果：[12, 23, 45, 17, 13, 67, 99]
第3轮排序结果：[12, 23, 17, 13, 45, 67, 99]
第4轮排序结果：[12, 17, 13, 23, 45, 67, 99]
第5轮排序结果：[12, 13, 17, 23, 45, 67, 99]
第6轮排序结果：[12, 13, 17, 23, 45, 67, 99]
插入排序
算法步骤
1、首先从第一个元素开始，该元素被认为是有序的；
2、取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
3、如果该已排好序的元素大于新元素，则将该元素移到下一位置；
4、重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。
代码实现
package com.example.helloworld;
import java.util.Arrays;
public class InsertSort {
public static void insertsort(int[] arr){
for (int i = 1; i < arr.length; i++){
int val = arr[i], j = i;
while (j > 0 && val < arr[j - 1]){
arr[j] = arr[j - 1];
j--;
}
arr[j] = val;
System.out.println("第" + i + "轮排序结果：" + Arrays.toString(arr));
}
}
public static void main(String args[]){
int[] arr_1 = {17,13,5,2,6,9};
System.out.println("array_1插入排序结果为：");
InsertSort.insertsort(arr_1);
}
}
array_1插入排序结果为：
第1轮排序结果：[13, 17, 5, 2, 6, 9]
第2轮排序结果：[5, 13, 17, 2, 6, 9]
第3轮排序结果：[2, 5, 13, 17, 6, 9]
第4轮排序结果：[2, 5, 6, 13, 17, 9]
第5轮排序结果：[2, 5, 6, 9, 13, 17]
算法比较
| 冒泡排序 | 插入排序 | |
|---|---|---|
| 平均时间复杂度 | O(n^2) | O(n^2) |
| 最好时间复杂度 | O(n) | O(n) |
| 最坏时间复杂度 | O(n^2) | O(n^2) |
| 空间复杂度 | O(1) | O(1) |
| 稳定性 | 稳定 | 稳定 |
| 适用情况 | 小规模数据或基本有序的数据 | 小规模数据或部分有序的数据 |
- 插入排序是从正向有序的，而冒泡排序是从逆向有序，冒泡排序是每次最后的一个值都为最大
- 插入排序是将无序的元素插入有序的元素序列中，插入后仍然有序；冒泡排序是比较相邻的元素，直到序列变成有序为止