一 冒泡排序
1.1 介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化： 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，再进行)
1.2 小结
(1) 一共进行 数组的大小-1次 大的循环
(2)每一趟排序的次数在逐渐的减少
(3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化
1.3 代码实现
public static void bubbleSort(int[] arr) {
int temp = 0; // 临时变量
boolean flag = false; // 标识变量，表示是否进行过交换
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
// 如果前面的数比后面的数大，则交换
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (!flag) { // 在一趟排序中，一次交换都没有发生过
break;
} else {
flag = false; // 重置flag!!!, 进行下次判断
}
}
}
二 选择排序
2.1 基本思想
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到 排序的目的。
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值， 与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值， 与 arr[n-2]交换，总共通过n-1(选出了n-1个，剩下那个不选比了) 次，得到一个按排序码从小到大排列的有序序列。
2.2 小结
- 一共有n-1轮
- 每轮的比较次数再递减，第一轮从0开始。之后递增
- 不是一发现当前最小值就马上交换（没有意义），而是记录下标最后一轮再交换
2.3 代码实现
public void select2(int[] arr) {
for(int i = 0 ;i<arr.length-1;i++) {
//第i个放最本轮最小（假定升序）的
int min = arr[i];
int minIndex = i;
for(int j = i+1;j<arr.length;j++) {
if(arr[j]<min) {
min = arr[j];
minIndex = j;
}
}
//一轮结束，开始交换
if(i!=minIndex) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
2.4 和冒泡比
更优秀，因为交换的次数少了
三 插入排序
3.1 基本思想
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序法思想: 插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有 序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排 序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
3.2 排序思路图
和打扑克摸牌一个道理
3.3 代码实现
//假定升序
public static void insertSort(int[] arr) {
int insertVal = 0;//待插入的值（无序列表的第一位下标）
int insertIndex = 0;（可能插入的下标）
//使用for循环来把代码简化
for(int i = 1; i < arr.length; i++) {//n-1次
//定义待插入的数
insertVal = arr[i];
insertIndex = i - 1; // 即arr[1]的前面这个数的下标（有序表的最后一个位置）
// 给insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置（如果大于等于说明就不用继续往下找了）
// 3. 就需要将 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
// 举例：理解不了，我们一会 debug
//这里我们判断是否需要赋值
if(insertIndex + 1 != i) {//等于就不用改了
arr[insertIndex + 1] = insertVal;
}
//System.out.println("第"+i+"轮插入");
//System.out.println(Arrays.toString(arr));
}
}
为什么arr[insertIndex + 1] = insertVal;?
分析退出循环的情况
- insertIndex < 0。此时 insertIndex=-1，说明当前插入值是最小的需要放到insertIndex+1=0的下标处
- insertVal >= arr[insertIndex].说明此时的插入值应该再insertIndex下标处的值后面。所以也需要
insertIndex+1
3.4 速度比较
比选择排序慢，因为在插入过程中。可能会不断往后移动数组元素
