0. 前言
排序算法中涉及到了两个概念：
原地排序：根据算法对内存的消耗情况，可以将算法分为原地排序和非原地排序，原地排序特指空间复杂度为 O(1) 的排序。
排序算法的稳定性：例如排序一个数组 [1, 5, 3, 7, 4, 9, 5]，数组中有两个 5，排序之后是 [1, 3, 4, 5, 5, 7, 9]，如果排序之后的两个 5 的前后顺序没有发生变化，那么称这个排序是稳定的，反之则是不稳定的。
1. 冒泡排序
冒泡排序是很经典的排序算法了，相邻的两个数据依次进行比较并交换位置。遍历一遍数组后，则有一个数据排序完成，然后再遍历 n 次，排序完成。示意图如下：
代码实现：
public class BubbleSort { private static void bubbleSort(int[] data){ int length = data.length; for (int i = length - 1; i > 0; i --) { //判断是否有数据交换，如果没有则提前退出 boolean flag = false; for (int j = 0; j < i; j ++) { if (data[j] > data[j + 1]){ int temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; flag = true; } } if (!flag){ break; } } } }
2. 选择排序
将要排序的数据分为了已排序区间和未排序区间，每次从未排序区间找到最小值，然后将其放到已排序区间的末尾，循环遍历未排序区间则排序完成。
示意图如下：
网络异常，图片无法展示
|
代码实现：
public class SelectionSort { public static void selectionSort(int[] data){ int length = data.length; for (int i = 0; i < length - 1; i++) { int min = i; for (int j = i + 1; j < length; j++) { if (data[min] > data[j]){ min = j; } } int temp = data[min]; data[min] = data[i]; data[i] = temp; } } }
3. 插入排序
和选择排序类似，插入排序也将数据分为了已排序区间和未排序区间，遍历未排序区间，每次取一个数据，将其插入到已排序区间的合适位置，让已排序区间一直保持有序，直到未排序区间遍历完排序则完成。
示意图如下：
代码实现：
public class InsertionSort { public static void insertionSort(int[] data){ int length = data.length; for (int i = 0; i < length - 1; i++) { int val = data[i + 1]; int j = i + 1; while (j > 0 && data[j - 1] > val){ data[j] = data[j - 1]; j --; } data[j] = val; } } }
插入排序为什么比冒泡排序更常用？
这两种排序的时间复杂度都是一样的，最好情况是 O(n)，最坏情况是 O(n2)，但是在实际的生产中，插入排序使用更多，原因在于两者数据交换的次数不同。冒泡排序需要进行三次交换，插入排序只要一次：
//冒泡排序数据交换 if (data[j] > data[j + 1]){ int temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; flag = true; } //插入排序数据交换 while (j > 0 && data[j - 1] > val){ data[j] = data[j - 1]; j --; }
在数据量较大的时候，两者性能差距就体现出来了。
