2.交换排序（冒泡排序，快速排序）

3.选择排序（选择排序，堆排序）

4.归并排序

[](

)一、插入排序

=========================================================================

插入排序属于内部排序法，是对内部欲排序的元素以插入的方式移动到合适的位置

即把所有的元素看成两部分，一部分是有序的，另外一部分是无序的，刚开始有序的部分为一个元素，而无序的部分则为n-1个元素，排序的时候将无序序列中第一个元素和有序队列进行比较，将其放到合适的位置，形成新的有序表。

 //插入排序

public static void insertionSort(int []array){

        for(int i=1;i<array.length;i++){

            int tmp=array[i];

            int j=i-1;

            for(;j>=0;j--){

                if(array[j]>tmp){//

                    array[j+1]=array[j];

                }else {

                    break;

                }

            }

            array[j+1]=tmp;

        }

    } 

插入排序的平均时间复杂度是O（n^2） 最好情况是O（n）最坏情况也是O（n^2），空间复杂度是O（1），稳定性 ：稳定

[](

)二、希尔排序

=========================================================================

希尔排序就是优化的插入排序，将一组数据分成n组，之后再组内进行交换即可，

给定组的值可以为固定的值，一般都为数组长度除二

 public static void shellSort(int []array){

        int []drr={5,2,1};

        for (int i = 0; i <drr.length ; i++) {

            shell(array,drr[i]);

        }

    }

    public static void shell(int []array,int gap){

        for(int i=gap;i<array.length;i++){

            int tmp=array[i];

            int j=i-gap;

            for(;j>=0;j=j-gap){

                if(array[j]>tmp){

                    array[j+gap]=array[j];

                }else {

                    break;

                }

            }

            array[j+gap]=tmp;

        }

    } 

希尔排序的平均时间复杂度为O（n^1.3~1.5），最好情况是O（n），最坏情况是n平方 。空间复杂度是O（1）。

稳定性： 不稳定。

[](

)三、冒泡排序

=========================================================================

优化冒泡排序就是插入一个boolean变量检查是否交换，如果没有交换说明已经有序即退出。

 public static void bubbleSort(int []array){

        for(int i=0;i<array.length-1;i++){

            boolean flg=false;

            for(int j=0;j<array.length-1-i;j++){

                if(array[j]>array[j+1]){

                    int tmp=array[j];

                    array[j]=array[j+1];

                    array[j+1]=tmp;

                    flg=true;

                }

            }

            if(flg==false){

                break;

            }

        }

    } 

冒泡排序时间复杂度为O（n^2） 最好情况是O（n）即数组就是有序的 遍历一边没有交换元素。空间复杂度为O（1）稳定性：稳定

[](

)四、选择排序

=========================================================================

 public static void selectSort(int []array){

        for(int i=0;i<array.length;i++){

            for(int j=i+1;j<array.length;j++){

                if(array[j]<array[i]){

                    int tmp=array[j];

                    array[j]=array[i];

                    array[i]=tmp;

                }

            }

        }

    } 

选择排序的时间复杂度最好最坏情况都是O（n^2） 空间复杂度为O（1）， 稳定性：不稳定

[](

)五、堆排序

========================================================================

堆排序就是先建立一个大堆，大堆的每一个子树的根都是最大的，然后尾巴元素和根交换，之后重新建大堆，再次找到最大的数放到根位置，继续交换即可

//堆排序 从小到大排序 应该是建大堆（能知道最上面是最大的）

    public static void heapSort(int []array){

        createHeap(array);

        int end=array.length-1;

       // while(){//循环 建立大堆 每次都是头最大 交换 尾巴节点

        while (end>0){

            int tmp=array[0];

            array[0]=array[end];

            array[end]=tmp;

            adjust(array,0,end);

            end--;

        }

        }

    public static void adjust(int []array,int parent,int len){

        int child=2*parent+1;

        while(child<len){

            if(child+1<len&&array[child+1]>array[child]){





> **本文已被[CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+真实项目实战+最新讲解视频】](https://codechina.csdn.net/m0_60958482/java-p7)收录，自学编程路线及系列技术文章等资源持续更新中...**