算法基础之排序算法大总结1！！
1. 冒泡排序
基础中的基础就是冒泡排序，冒泡排序的核心思想就是比较，通过比较前后两个元素并换位实现排序，由两个for循环进行实现
- 外层for：控制排序的次数
- 内层for：控制每次的比较和交换
public void bubbleSort(int[] arr){
//冒泡排序的时间复杂度为O(n*n)
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length-1 -j ; i++) {
if (arr[i] > arr[i+1]){
swap(arr,i,i+1);
}
}
}
}
public void swap(int [] arr,int i,int j) {
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}这里实际上是可以进行优化的，比如说我的数组是10个元素，在外层到达第三个的时候，我内层for循环完了都没有进行过交换，说明我后面的元素实际上是已经排序好了的，那么这时我就可以直接退出外循环返回结果了
public static void bubbleSort(int[] arr){
//冒泡排序的时间复杂度为O(n*n)
boolean flag = false;//用于优化冒泡排序，判断是否进行过交换
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length-1 -j ; i++) {
if (arr[i] > arr[i+1]){
swap(arr,i,i+1);
}
}
//如果没有进入三角交换则证明数组已经有序，直接退出循环即可
//如果进入了三角交换，把flag赋值为false，来判断下一次循环是否进入三角交换
if (flag == false){
break;
}else {
flag = false;
}
}
}
public static void swap(int [] arr,int i,int j) {
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}算法分析：冒泡排序不在乎数组中的数据是什么情况，有序无序都行，反正直接暴力破解一切。因此是最稳定的排序算法
2. 选择排序算法
也是两层for循环，并且这个算法无论数组中是什么数据情况都是O（n2）的复杂度
- 外层for：控制排序的次数
- 内层for：找到最小值索引位置并与外层for循环所在位置交换
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i; // 记录最小值索引，默认值为i
minIndex = getMinIndex(arr, i, minIndex);//找到最小值所在索引位置
// 交换当前索引 i 和最小值索引 minIndex 两处的值
if (i != minIndex) {
swap(arr, i, minIndex);//交换位置
}
}
}
private static int getMinIndex(int[] arr, int i, int minIndex) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 遍历 i+1~length 的值，找到其中最小值的位置
}
}
return minIndex;
}
public static void swap(int [] arr,int i,int j) {
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}算法分析：了解即可，没啥用的算法，从什么方面都被薄纱
3. 插入排序算法
也是一个两层for循环的算法，核心逻辑
- 外循环：排序次数，假设 当前为i
- 内循环：假设i之前的数组是排序好的，拿到i之后的下一个数据，从后往前循环 i之前数组 找到位置进行插入
public static int[] insertionSort(int[] arr){
for(int i=1; i<arr.length; i++){
for(int j=i; j>0; j--){
if(arr[j]<arr[j-1]){
swap(arr, j, j-1);
}
}
}
return arr;
}
public static void swap(int [] arr,int i,int j) {
int temp = 0;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}优化一下，这里两层for循环每次都要赋值一个temp变量有点资源浪费，实际上没必要，这个变量就是要插入的值，直接在外层for循环进行定义就好了
public static int[] sort2(int[] arr){
for(int i=1; i<arr.length; i++){
int temp = arr[i];//保存每次需要插入的那个数
int j;
for(j=i; j>0&&arr[j-1]>temp; j--){
arr[j] = arr[j-1];
}
arr[j] = temp;//将需要插入的数放入这个位置
}
return arr;
}4. 希尔排序算法
希尔排序是首个时间复杂度突破O(n^2)的排序算法，它是对前面说到的插入排序的改进版，定义一个增量，然后根据这个增量将几个元素分成一组，最终可能会得到很多个组，在组内进行插入排序，每个组都完成排序后再缩小增量，再排序，直到增量为1，也就是所有排序都成为了一组，这个时候就变成了最简单的插入排序了
eg：一个数组是[2,11,13,3,3,4,5,9.14,]
第一次先分为[2，11,13, ]和 [4,5,9,14] 两组
第二次就分为4组
第三次就分为八组刚刚好就是增量为1的情况，此刻已经排序完成
希尔排序也是两层for循环实现，但是由于分组进行插入排序的思想突破了时间复杂度。
eg：极限情况下，大数全部在前面，小数全部在后面，那么插入排序到后面每次交换到要把排序好的整个数组进行移位。如果使用希尔排序的话，第1000位可以直接和第333位进行交换！！，发现新大陆了叭
public static void ShellSort(int[] arr, int gap) {
//确定新一轮分组的增量
gap = gap / 2;
//对数组进行分组
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < arr.length; j += gap) {
//获取当前元素，然后在本组内部向前比较并排序
int current = arr[j];
for (int k = j - gap; k >= i; k -= gap) {
if (arr[k] > current) {
//插入
arr[k + gap] = arr[k];
arr[k] = current;
}
}
}
}
if (gap > 1) {
ShellSort(arr, gap);
}
}