什么是冒泡排序
冒泡排序的特点是每次都是相邻的两个数进行比较，是一个比较简单的排序算法其实现如下
package sort;
/**
* @author TioSun
* 冒泡排序
*/
public class BubbleSort {
/**
* 冒泡排序
* @param a 待排序数组
* @param n 数组大小
*/
public void sort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
// 相邻的两位数进行比较
if (a[j] > a[j+1]) {
// 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
// 表示本次循环有发生交换动作
flag = true;
}
}
// 如果某次循环没有发生交换，则说明数组有序，可以提前退出循环
if (!flag) {
break;
}
}
}
}
冒泡排序是稳定排序吗？
从代码中我们可以看出，相邻的两个元素相等时，我们是不做交换动作的，所以冒泡排序是稳定排序
冒泡排序是原地排序吗？
从代码中我们可以看到，我们只用了常量级的额外空间，所以是原地排序
冒泡排序的时间复杂度
最好的情况是待排序数组已经是有序的，这个时候冒泡排序只需要遍历一次数组即可完成排序，所以最好情况的时间复杂度是O(n)，最坏情况是数组正好和排序结果相逆，这是需要的时间复杂度是O(n2)。那么平均时间复杂度是多少？这里大家可以去了解下有序度的相关知识，篇幅原因暂时不讲了。可以给出的是平均时间复杂度还是O(n2)。
什么是插入排序
插入排序的思维来自于向有序数组中插入一个数据的动作。对于待排序数组，我们将其划分成两块区域，有序区和无序区。初始有序区只有数组的第一个元素，通过向后遍历，不断向有序区插入数据从而完成排序动作。
package sort;
/**
* @author TioSun
* 插入排序
*/
public class InsertionSort {
/**
* 插入排序
*
* @param a 待排序数据
* @param n 数据量
*/
public void sort(int[] a, int n) {
// 无需排序
if (n <= 1) {
return;
}
for (int i = 1; i < n; ++i) {
// 需要插入的数据
int value = a[i];
int j = i;
// 查找插入的位置，因为i是待插入数据的下标，所以i-1的位置是有序区的终端（0是起始端）
for (; j > 0; --j) {
// 将待插入数据和左边的数据比较
if (a[j-1] > value) {
//右移数据以腾出位置给待插入数据
a[j] = a[j-1];
} else {
break;
}
}
// 插入数据
a[j] = value;
}
}
}
插入排序是稳定排序吗
当数值相同时，我们并不会把后面的数据插入到前面去，所以插入排序是稳定排序。
插入排序是原地排序吗
插入排序只使用了常数级的额外空间，所以是原地排序。
插入排序的时间复杂度
和分析冒泡排序的方式相同，插入排序的最好时间复杂度是O(n)（待排序数组已符合要排序顺序），最坏时间复杂度是O(n2)（待排序数组和要排序顺序相逆），平均时间复杂度是O(n2)。
为什么我们更常用插入排序
从上面的分析来看，不管是稳定性、空间复杂度还是时间复杂度，冒泡排序和插入排序的对比都是一致的，那为什么在两种排序算法选择时我们更倾向于插入排序呢？
我们可以对比下两种算法的核心部分
// 冒泡排序
if (a[j] > a[j+1]) {
// 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
// 表示本次循环有发生交换动作
flag = true;
}
// 插入排序
if (a[j-1] > value) {
//右移数据以腾出位置给待插入数据
a[j] = a[j-1];
} else {
break;
}
可以比较清楚的对比出，冒泡排序一次交换需要进行三次赋值动作，而插入排序只需要进行一次赋值动作。可能会有同学认为这差异很大吗？其实差异很大的，我设了两万个随机数，分别用冒泡排序和插入排序对其进行排序，其时间差异如下图：
image.png
能明显看出数据量大的时候，插入排序所消耗的时间更少
网友评论