冒泡排序、插入排序、选择排序
冒泡排序（Bubble Sort）
冒泡排序只会操作相邻的两个数据。两两比较，将较大的数换到后边。
代码如下：
/**
* 冒泡排序
* 两两比较，将较大的数移到后边。
*
* @param a
* @param n
*/
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; i++) {
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;
}
}
}
}
这里我们还可以进行优化，如果某次冒泡之后已经没有数据可以交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。代码如下：
/**
* 优化后的冒泡排序
*
* @param a
* @param n
*/
public void bubbleSortOptimize(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;
}
}
插入排序（Insertion Sort）
我们将待排序的数据分为两个区间，已排序区间和未排序区间。初始状态下，已排序区间为空。
插入算法的核心思想是取未排序区间的元素，在已排序区间中找到合适的位置插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
代码如下：
/**
* 插入排序
* 将数据插入到有序数组中。
*
* @param a
* @param n
*/
public void insertSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; i++) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; j--) {
if (a[j] > value) {
a[j + 1] = a[j];// 数据移动
} else {
break;
}
}
a[j + 1] = value;// 插入数据
}
}
选择排序（Selection Sort）
跟插入排序类似，选择排序也区分已排序区间和未排序区间。初始状态下，已排序区间为空。 选择排序的核心是每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
代码如下：
/**
* 插入排序
* 从未排序区间中找到最小元素，将其放到已排序区间的末尾。
*
* @param a
* @param n
*/
public void selectSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n - 1; i++) {
// 查找最小值的角标
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 减少无用的交换。
if (minIndex == i) {
continue;
}
// 交换
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}