常见排序算法

1.冒泡排序

重复走访要排序的数列，一次比较两个元素，若较小元素再后则交换，能看到越小的元素会经由交换慢慢浮到数列的顶端。
时间复杂度o(n^2)，空间复杂度是o（1），稳定性排序
适用于数据规模小

for(int i=0;i<arr.length;i++) {
            // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
            boolean flag=false;
            for(int j=0;j<arr.length-i-1;j++) {
                //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
                if(arr[j]>arr[j+1]) {
                    //进行交换
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
           if(!flag) {
              // 如果没有交换则直接返回
               break;
           }
               
        }
    }

2.插入排序

对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：最好是O(n)，平均是O(n^2)，稳定排序

/**插入排序
     * @param arr
     * 它的工作原理是通过构建有序序列，对于未排序数据，
     * 在已排序序列中从后向前扫描，找到相应位置并插入。
     * 插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，
     * 为最新元素提供插入空间。
     * 
     */
    public static void insertArr(int[] arr) {
        if(arr.length<=0) {
            return;
        }
        for(int i=0;i<arr.length;i++) {
            for(int j=i;j>0;j--) {
                if(arr[j]<arr[j-1]) {
                    //进行交换
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
    }
    
    

3.选择排序

每次在没排序序列中查找最小元素（最大元素），将最小元素（最大元素放到）起始位置。
时间复杂度O(n^2),空间复杂度o(1),不稳定排序
适用于数据规模小

/** 选择排序
     * @param arr 要排序的数组
     * 每次在未排序的中找到最小的元素于起始元素进行交换，起始位置是指在没排序的序列的第一个位置
     */
    public static void selectSort(int[] arr) {
        if(arr.length<=1) {
            return ;
        }
        //只需要n-1趟即可
        for(int i=0;i<arr.length-1;i++) {
            int minIndex=i;//记录最小数的位置
            for(int j=i+1;j<arr.length;j++) {
                if(arr[minIndex]>arr[j]) {
                    minIndex=j;
                }
            }
            //判断是否已经交换
            if(minIndex!=i) {
                //交换
                int temp=arr[minIndex];
                arr[minIndex]=arr[i];
                arr[i]=temp;
            }
        }
        
    }

希尔排序

将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序,把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入排序进行排序；小组的个数逐次缩小，当完成了所有的数据元素都在一个小组内的排序后，排序过程结束。所以希尔排序又称作缩小增量排序。
时间复杂度：O(nlogn)~O(n^2),空间复杂度：O(1)，不稳定
适合数据规模大。

/**希尔排序
     * @param arr 要排序的数组
     */
    public static void shellSort(int[] arr) {
        if(arr.length<=0) {
            return;
        }
        //计算最大间隔，公式h=h*3+1;
        int h=1;
        while(h<arr.length/3) {
            h=h*3+1;
        }
        //缩小增量进行排序
        while(h>0) {
            //进行排序
            
            int i,j;//i表示当前待插入数的下标，j表示本次被比较的有序数位置
            for(i=h;i<arr.length;i++) {
                int waitInsert=arr[i];//等待插入的数
                j=i-h;//比较位置初始化，也就是有序序列的最后一个位置，从后往前
                //大于或等于等待插入的数值大小，则该数右移一个间隔大小，然后进行下一次比较
                while(j>=0&&arr[j]>=waitInsert) {
                    arr[j+h]=arr[j];
                    j=j-h;
                }
                //插入的位置一定是上一次比较的数的位置，也就是j+h的位置。（注意到j-h的时机即可理解）
                arr[j + h] = waitInsert;
            }
            //缩小增量，公式：h = (h - 1) /3
            h = (h - 1) / 3;
        }
    }

堆排序

近似完全二叉树的结构，子结构的键或索引总是小于（活大于）其父节点
时间复杂度O(nlogn)，空间复杂度O(1)，不稳定。
数据规模较大，相比快排好处事不会出现最坏情况，需要的辅助空间少。

大顶堆的公式：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
小顶堆的公式: arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]

快速排序是不稳定的排序，归并是稳定排序
快速排序和归并排序参考

image.png

参考链接：https://www.cnblogs.com/guoyaohua/p/8600214.html
https://www.cnblogs.com/wuxiangli/p/6399266.html