:比较n-1趟，时间复杂度 O(n^2) 空间复杂度O(1)
基本思想：通过对 待排序 序列从前向后（从小到大），依次比较相邻元素的值，若发现逆序，则交换，使得值较大的元素不断后移，就像水底的气泡一样逐渐上冒 优化： 因为排序的过程中，各个元素不断的接近自己的最终位置，如果一趟比较下来都没有发生交换， 说明序列有序了，就可以提前结束排序了。因此我们可以在排序的过程中设置一个标志flag判断
元素是否发生过交换，从而减少不必要的开销
public static void bubbleSort(int arr[]){
// int tmp =0;//用来存放交换值的临时变量
// int n = arr.length;
// for (int i = 0; i < n-1; i++) {//N-1次
// for (int j = 1; j < n -i ; j++) {//n-i 每一趟比较无序序列的最后一个元素下标+1
// if (arr[j-1] > arr[j]){
// tmp = arr[j - 1];
// arr[j - 1] = arr[j];
// arr[j] = tmp;
// }
// }
// }
//优化
int tmp =0;//用来存放交换值的临时变量
int n = arr.length;
boolean flag = true;//用来判断每趟比较是否发生交换
for (int i = 0; i < n-1; i++) {//N-1次躺比较
flag = true;
for (int j = 1; j < n -i ; j++) {//n-i 每一趟比较无序序列的最后一个元素下标+1
if (arr[j-1] > arr[j]){//发生交换
flag = false;
tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
if(flag){//未发生交换，说明序列已经有序，则跳出循环
break;
}
}
}
选择排序
:比较n-1趟， 时间复杂度O(n^2) 空间复杂度 O(1)
基本思想：从预排序的数据中，按指定的规则选取出某一元素，再依据规定交换位置后达到排序的目的 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换 ，第二次从第arr[1]~arr[n-1]中选取最小值与arr[i]交换...第n-1次从arr[n-2]~arr[n-1]中选取最小值交换，此时数据就已经排好序了；总共进行n-1次交换
public static void selectSort(int arr[]){
int n = arr.length;
int min = 0; //假设arr[0]为最小值
int minIndex = 0;//记录最小值下标
for (int i = 0; i < n -1; i++) { //n-1 次循环
min = arr[i]; //假设arr[0]为最小值
minIndex = i; //每趟重置最小值和最小值下标
for (int j = i+1; j < n; j++) {//遍历 arr[j]~arr[n-1],因为每次都设假定待排序序列第一个为最小值，所以可以直接从第二个值开始遍历
if(min > arr[j]){//发现更小的值，更新最小值和最小值下标
min = arr[j];
minIndex = j;
}
}
if(min != arr[i]){
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
插入排序
:比较n-1趟， 时间复杂度 O(n^2) 空间复杂度 O(1)
基本思想： 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素， 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较， 将它插入到有序表中的适当位置，使之成为新的有序表。
public static void insertSort(int[] arr){
int n = arr.length;
//设置哨兵，用来存放插入值和判断数组边界
int insertIndex = 0;//记录有序队列的右边界
int insertVal = 0;//记录插入值下标
for (int i = 1; i < n; i++) {
insertIndex = i-1;
insertVal = arr[i];
while(insertIndex >= 0 && insertVal < arr[insertIndex]){//逆序遍历有序列表，找到插入位置
arr[insertIndex+1] = arr[insertIndex];
insertIndex--;//每次遍历后前移一位
}
//插入值
arr[insertIndex+1] = insertVal;
System.out.println("第"+i+"轮排序的结果："+Arrays.toString(arr));
}
}
希尔排序
希尔排序（缩小增量排序） 平均时间复杂度 O(n logn) 空间复杂度O(1)
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。 基本思想 ：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时， 整个文件恰被分成一组，进行最后一次插入排序，然后算法便终止
public static void shellSort(int[] arr){
int n = arr.length;
// //交换法
// int tmp = 0;
// for (int gap = n/2; gap >0 ; gap /= 2) {
// for (int i = gap; i < n; i++) {//遍历所有元素（共 gap 组，每组有 n/gap个元素）
// for(int j = i-gap; j >=0 ; j -= gap){//逆序遍历数组
// if(arr[j] > arr[ j + gap]){//交换法
// tmp = arr[j];
// arr[j] = arr[j+gap];
// arr[j+gap] = tmp;
// }
// }
// }
// System.out.println("第"+"轮排序的结果："+Arrays.toString(arr));
// }
//设置哨兵在分界处
int index = 0;
int tmp = 0;
int count = 1;
for (int gap = n/2; gap > 0 ; gap /= 2) {
//从gap处开始，对每组进行排序
for (int i = gap; i < n; i++) {
index = i;
tmp = arr[i];
if (index - gap >= 0 && tmp < arr[index -gap] ){
//寻找插入位置
arr[index] = arr[index-gap];//后移
index -= gap;
}
//插入对应位置
arr[index] = tmp;
}
System.out.println("第"+(count++)+"轮排序的结果："+Arrays.toString(arr));
}
}
