1、选择排序
给定数组arr，其长度为n。实现思路：
- 遍历数组，从0 ~ n - 1，找到最小的，找到后，和数组的第一个元素互换位置
- 继续新一轮遍历，从1 ~ n - 1，找到最小的，找到后，和数组的第二个元素互换位置
- 再来一轮遍历，从2 ~ n - 1，找到最小的，找到后，和数组的第三个元素互换位置
- ……
- 如此，遍历完数组，即可完成排序
核心思路：每次遍历，把剩下的里面最小的元素扔前面去，0到n-1的范围找最小的扔前面，再1到n-1的范围找最小的，以此类推。代码实现：
public class Sort {
/**
* 选择排序
*/
public static void selectSort(int[] arr) {
// 数组长度为1时，不用排序
if (null == arr || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
// 最小值的索引，开始i=0
int minValueIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 如果i的下一个元素比i小，则覆盖最小值索引
minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
}
// 0 ~ n-1 的范围都比较完了，把最小值的和第一个元素互换
int temp = arr[i];
arr[i] = arr[minValueIndex];
arr[minValueIndex] = temp;
// 一轮循环结束，找到了第一小的元素，并放在了数组首位
// 接下来开下一轮循环，找第二小的元素，放在数组的第二位
}
}
}
2、冒泡排序
前面选择排序是，我找到最值后，手动给它放到数组首位。冒泡则是：第n个元素和第n+1个元素对比，交换，让大的那个放右边，接着n+1和n+2位置的元素对比，依旧大的放右边。如此，比较完一轮，就会让第一大的元素像一个气泡一样，一步步的走到了数组末尾的位置。再进行第二轮，第二大的元素也会像一个气泡一样，一步步的走到了数组倒数第二的位置。
代码实现：
public class Sort {
/**
* 冒泡排序
*/
public static void bubbleSort(int[] arr) {
// 数组长度为1时，不用排序
if (null == arr || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
// 设arr.length = n
// 外层出循环第一轮，end = n - 1, 先处理0 ~ n-1
// 外层循环第二轮，end = n - 2, 先处理0 ~ n-2
// 外层循环最后一轮，end = 1, 先处理0 ~ 1
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
}
3、插入排序
插入排序，正如这个名字，就像打牌一样，整牌时，比如现在最大的放在左边，那抽到一张新牌后，从右往左看，一个个比较，然后把新进来的牌插入到合适的位置。插入排序也是这个思路。也就是说，实现步骤是：
- 先保证0 ~ 0 号元素有序（即保证第一张牌有序）
- 再保证0 ~ 1号元素有序（即保证前两张牌有序）
- 再保证0 ~ 2号元素有序（即保证前三张牌有序），但前两张已经有序，此时只需处理第三张牌即可
- ……
- 保证0 ~ n - 1号元素有序，但前n - 2张已有序，此时只需处理最后一张牌，一个个比，把它插入到合适的位置即可
到这儿，想到一点，算法，即解决问题的步骤，把生活中怎么解决同样问题的行为，翻译成代码，就是答案。此外，解一道题，应该先举一个简单具体的例子，分析清楚后，再逐步扩大数据量来分析。
public class Sort {
/**
* 插入排序
*/
public static void insertSort(int[] arr) {
// 数组长度为1时，不用排序
if (null == arr || arr.length < 2) {
return;
}
// 初始end = 1,先保证0~1有序，后面end+1,就是保证0~2有序
// end控制末尾的边界
for (int end = 1; end < arr.length; end++) {
// end - 1 > 0，说明左边还有元素可以比较
// arr[end - 1] < arr[end]不满足的话，说明有序，也不用交换
int newNumIndex = end;
while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] < arr[newNumIndex]) {
int temp = arr[newNumIndex - 1];
arr[newNumIndex - 1] = arr[newNumIndex];
arr[newNumIndex] = temp;
// 交换后，和新的左边的数继续比，直到越界或者遇到比它大的数字，停止比较和交换
newNumIndex--;
}
}
}
}
优化下：
public class Sort {
/**
* 插入排序2
* 用for嵌套
*/
public static void insertSort2(int[] arr) {
if (null == arr || arr.length < 2) {
return;
}
// 初始end = 1,先保证0~1有序，后面end+1,就是保证0~2有序
// end控制末尾的边界
for (int end = 1; end < arr.length; end++) {
// pre为当前数的左侧方向的前一个数
for (int pre = end - 1; pre >= 0 && arr[pre] < arr[pre + 1]; pre--) {
int temp = arr[pre];
arr[pre] = arr[pre + 1];
arr[pre + 1] = temp;
}
}
}
}
