基础算法-冒泡排序，插入排序，选择排序
本文图片来在极客时间-王争老师的《数据结构与算法之美》
冒泡排序（Bubble Sort）
算法说明
每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
例如：要对一组数据 4，5，6，3，2，1，从小到大进行排序。第一次冒泡操作的详细过程如下：
步骤说明
假设要对N个元素进行冒泡排序，执行的步骤如下：
比较相邻的元素。如果前者>后者，则交换两者的位置。
按顺序对每一组相邻元素做步骤1的工作，直到结束（需要执行了N-1次比较工作）。
以此类推，执行N-1次的步骤2，即可完成冒泡排序。
JAVA代码
package cn.hgy.data.algorithm;
package cn.hgy.data.algorithm;
/**
* 冒泡排序
* <pre>
* 算法介绍：遍历待排序的数，每次选出最大的数添加到合适的位置
* 时间复杂度：最优-O(n)，最坏-O(n^2),
* </pre>
*
* @author guoyu.huang
* @version 1.0.0
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arrays = {4, 5, 6, 3, 2, 1};
int[] sortArrays = sort(arrays);
for (int i = 0; i < sortArrays.length; i++) {
System.out.print(sortArrays[i] + " ");
}
}
/**
* 排序
* <pre>
* 两个优化点：
* 1. 如果进行一轮的比较遍历后，没有发生过替换操作，则表示当前已是有序状态
* 2. 每进行一轮比较遍历后，在进行第i轮之后，数组尾部的n-i到n的数是有序的，无需再判断
* </pre>
*
* @param content
*/
public static int[] sort(int[] content) {
for (int i = 0; i < content.length; i++) {
// 优化点1：有序性标识符
boolean ordinalFlag = true;
// 优化点2：在进行i轮之后，数组尾部的n-i到n的数是有序的
for (int j = 0; j < content.length - i - 1; j++) {
if (content[j] > content[j + 1]) {
ordinalFlag = false;
int temp = content[j + 1];
content[j + 1] = content[j];
content[j] = temp;
}
}
// 优化点1：进行一轮的比较遍历后，没有发生过替换操作，则表示当前已是有序状态
if (ordinalFlag) {
break;
}
}
return content;
}
}
插入排序（InsertionSort）
算法说明
我们将待排序的元素分为两个区间，已排序区间和未排序区间。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间的元素一直有序。
例如：要对一组数据 4，5，6，3，2，1，从小到大进行排序。插入排序的详细过程如下：
步骤说明
假设要对N个元素进行插入排序，执行的步骤如下：
第一次取第一个元素作为已排序区间，后续的N-1个元素作为未排序区间。
取未排序区间的第一个元素，在已排序区间找到合适的位置，并保证已排序区间还是有序的。
以此类推，执行N-1次的步骤2，即可完成插入排序。
JAVA代码
package cn.hgy.data.algorithm;
/**
* 插入排序
* <pre>
* 算法介绍：每次从未排序中选择第一个数添加到已排序的合适位置
* 时间复杂度：最优O(n)，最坏O(n^2)
* </pre>
*
* @author guoyu.huang
* @version 1.0.0
*/
public class InsertionSort {
public static void main(String[] args) {
int[] arrays = {4, 5, 6, 3, 2, 1};
int[] sortArrays = sort(arrays);
for (int i = 0; i < sortArrays.length; i++) {
System.out.print(sortArrays[i] + " ");
}
}
/**
* 排序
* <pre>
* 优化点：
* 1. 如果待排序的元素大于有序区的最大元素则直接在尾部插入
* 2. 等已排序区间的元素都移动好位置，再将元素插入指定位置，减少赋值操作
* </pre>
*
* @param content
*/
public static int[] sort(int[] content) {
for (int i = 0; i < content.length; i++) {
int temp = content[i];
// 优化点2：记录待插入的位置
int j = i - 1;
for (; j >= 0; j--) {
if (content[j] > temp) {
content[j + 1] = content[j];
} else {
// 优化点1：如果待排序的元素大于有序区的最大元素则直接在尾部插入
break;
}
}
// 优化点2：将元素插入指定位置，减少赋值操作
content[j + 1] = temp;
}
return content;
}
}
选择排序
算法说明
将待排序的元素分为两个区间，已排序区间和未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
例如：要对一组数据 4，5，6，3，2，1，从小到大进行排序。选择排序的详细过程如下：
步骤说明
假设要对N个元素进行选择排序，执行的步骤如下：
所有元素都在未排序区间
找出最小的数和未排序区间的第一个元素进行位置替换。
以此类推，执行N-1次的步骤2，即可完成选择排序。
JAVA代码
package cn.hgy.data.algorithm;
/**
* 选择排序
* <pre>
* 算法介绍：每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾
* 时间复杂度：最优O(n)，最坏O(n^2)
* </pre>
*
* @author guoyu.huang
* @version 1.0.0
*/
public class SelectionSort {
public static void main(String[] args) {
int[] arrays = {4, 5, 6, 3, 2, 1};
int[] sortArrays = sort(arrays);
for (int i = 0; i < sortArrays.length; i++) {
System.out.print(sortArrays[i] + " ");
}
}
/**
* 排序
*
* @param content
*/
public static int[] sort(int[] content) {
for (int i = 0; i < content.length; i++) {
int min = content[i];
int index = i;
// 每次从未排序中找出最小的值，将其插入已排序数组的尾部
for (int j = i; j < content.length; j++) {
if (content[j] < min) {
index = j;
min = content[j];
}
}
content[index] = content[i];
content[i] = min;
}
return content;
}
}
总结
分析维度一：时间复杂度
冒泡排序
最好时间复杂度：O(n)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
插入排序
最好时间复杂度：O(n)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
选择排序
最好时间复杂度：O(n^2)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(n^2)
分析维度二：空间复杂度
冒泡排序
O(1)
插入排序
O(1)
选择排序
O(1)
分析维度三：是否稳定
稳定排序是指在原有的顺序上，如果满足条件，还能够保留原有的顺序。
例如：订单按金额和时间来排序，如果是稳定的排序算法，先按时间排序之后，再按金额排序。即可实现，如下图：
冒泡排序
在比较替换的代码中，只处理大于的数据，相等的数据保持位置不变，所以是稳定的。
插入排序
在比较替换的代码中，只处理大于的数据，相等的数据保持位置不变，所以是稳定的。
选择排序
选择排序应该会互换元素之间的位置，所以会导致原有的顺序发生变化，所以不算稳定排序。
例如：5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。
冒泡排序 vs 插入排序
既然时间复杂度，空间复杂度一样，也都是稳定排序。那选择哪种排序更好呢？查看代码可知，一次交换中，插入排序的赋值操作为1次，冒泡排序的赋值操作为3次。插入排序更好一些。