稳定算法很重要，稳定算法比较次数少。

插入排序：

类比就是打扑克，
假设有个这样的问题：打扑克。分成两部分：一部分是你手里的牌（已经排好序），一部分是要拿的牌（无序）。把一个无序的数列一个个插入到有序数列中。一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？我们只要遍历数组，找到数据应该插入的位置将其插入即可。画图演示：以上这种往一个有序的集合里面插入元素，插入后序列仍然有序这就是插入排序算法思路。理解起来不难吧。那么插入排序具体是怎么实现呢？具体步骤如下：1.将数组分成已排序段和未排序段。初始化时已排序端只有一个元素2.到未排序段取元素插入到已排序段，并保证插入后仍然有序3.重复执行上述操作，直到未排序段元素全部加完。有几种数据结构，用什么数据结构来实现。数组，链表，2个数组。

代码实现：

        int n = arr.length;
        for(int i = 1;i<n;i++){//未排序数组
            int j = i-1;//排序数组的末尾
            int data = arr[i];
            for(;j>=0;j--){
                if(arr[j]>data){
                    //数组向后移动
                    arr[j+1] = arr[j];
                    continue;
                }
                //找到比插入数据小的位置，跳出循环
                break;
            }
            arr[j+1]=data;//给新的数组位置赋值
        }

希尔排序

来看一个具体的过程：
按照一个增量分段：add=n/2 n=10 =>5,2,1
7 8 9 0 4 3 1 2 5 10我们取的这个增量分别就是5 2 1
7 8 9 0 4 3 1 2 5 10:分出来的数组元素都是一样的
完成一次排序：3 1 2 0 4 7 8 9 5

3 2 4 8 5：取增量为2的分为一组了
最后一次我们就取增量为1的分组：就是一个完整的序列。

希尔排序是插入排序的增强版本，设置步长就是为了使break执行的更多。

 int n = arr.length;
        for (int add = n / 2; add >= 1; add /= 2) {
            for (int i = add; i < n; i += add) {//未排序数组
                int j = i - add;//排序数组的末尾
                int data = arr[i];
                for (; j >= 0; j -= add) {
                    if (arr[j] > data) {
                        //数组向后移动
                        arr[j + add] = arr[j];
                        continue;
                    }
                    break;
                }
                arr[j + add] = data;//给新的数组位置赋值
            }
        }

归并排序

分析时间复杂度：nlogn

 public static void megerSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            //左边开始递
            megerSort(arr, left, mid);
            //右边开始递
            megerSort(arr, mid + 1, right);
            //开始合并数组
            mergeArrarys(arr, left, mid, right);
        }
    }
    //合并数组
    private static void mergeArrarys(int[] arr, int left, int mid, int right) {
        //创新新的数组
        int[] tmp = new int[arr.length];
        int point1 = left;//左边数组的第一个
        int point2 = mid + 1;//右边数组的第一个
        int loc = left;//新的数组的开始位置
        while (point1 <= mid && point2 <= right) {
            if (arr[point1] < arr[point2]) {
                //左边小的话,进入临时数组中
                tmp[loc] = arr[point1];
                point1++;
                loc++;
            } else {
                tmp[loc] = arr[point2];
                point2++;
                loc++;
            }
        }
//
        //左边的数组可能没有完，继续添加在临时数组中
        while (point1 <= mid) {
            tmp[loc++] = arr[point1++];
        }
        //右边的数组可能没有完，继续添加在临时数组中
        while (point2 <= right) {
            tmp[loc++] = arr[point2++];
        }
        //复制临时数组到原数组
        for (int i = left; i <= right; i++) {
            arr[i] = tmp[i];
        }
    }

选择排序

快速排序

package com.sort;
/**
 * @author yangkang
 * @version 1.0
 * @description: 插入排序
 * @date 2022/3/12 23:39
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9, 13, 11, 10, 12, 5, 6};
        //9,13
        //9,13,13,10,12,5,6
        //9,11,13,10,12,5,6
        insertSort2(arr);
//        insertSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void insertSort2(int[] arr) {
        int n = arr.length;
        for(int i = 1;i<n;i++){
            int data = arr[i];
            int j = i-1;
            for(;j>=0;j--){
                if(arr[j]>data){
                    arr[j+1] = arr[j];
                    continue;
                }
                break;
            }
            arr[j+1] = data;
        }
    }
    private static void insertSort(int[] arr) {
        int n = arr.length;
        //9, 13, 11, 10, 12, 5, 6
        for(int i = 1;i<n;i++){//为排序的数组开始，从下标1开始
            int data = arr[i];
            int j =i-1;//排序的末尾
            for(;j>=0;j--){
                if(arr[j]>data){
                    arr[j+1] = arr[j];//数组往后面移动
                    continue;
                }
                break;//找到了比他小的值
            }
            arr[j+1] = data;
        }
    }
}