目录

一.插入排序

1.插入排序思想

2.动态图形演示

 3.插排思路与图解

4.插入排序代码实现（升序）

5.时间复杂度，空间复杂度及稳定性

6.应用场景

二.希尔排序

1.引言

2.希尔排序思想

3.希尔排序动图

4.希尔排序思路图解

​ 5.代码实现

 6.时间复杂度，空间复杂度及稳定性分析

7.应用场景

三.选择排序（升序）

1.排序思想

2.选择排序动态图示

3.思路图解

 4.代码实现

5.时间复杂度，空间复杂度及稳定性分析

6.应用场景

四.堆排序

1.堆排序的排序思想

2.堆排序动图演示

 3.思路图解及代码实现

4.时间复杂度，空间复杂度及稳定性

5.应用场景

五.冒泡排序

1.排序思想

2.冒泡排序动图演示

3.冒泡排序图解

4.冒泡排序代码：

 5.时间复杂度，空间复杂度及稳定性

6.应用场景

六.快速排序

1.快速排序思想

2.快速排序动图演示

 3.思路图解

5.时间复杂度，空间复杂度及稳定性分析

6.应用场景

七.归并排序

1.归并思想

2.归并排序动图演示

 3.实现归并的思路图解

4.代码实现

八.计数排序

1.排序思想

2.应用场景

3，思路图解​

 4.代码实现

5.时间复杂度，空间复杂度及稳定性

6.应用场景

---

一.插入排序

1.插入排序思想

就是将待排序的数字插入到已经排序好的指定位置即可，直到所有需要排序的数字都插入到序列即可，从而得到一个有序的序列。（相当于我们平常玩扑克牌时将接到的牌插入到指定的位置）

2.动态图形演示
 

 3.插排思路与图解

4.插入排序代码实现（升序）

（1）控制排序的次数，保存需要插入的值。

（2）将大的元素向后移，找到合适的位置。

（3）将元素插入指定位置，然后继续执行上述操作。

（4）这里需要注意在找的时候可能会到最前面，需要注意数组越界问题。

代码实现：

//插入排序(升序)
    public static void insertSort(int[] arr){
        //排序的次数
        for(int i=1;i<arr.length;i++){
            int end=arr[i];//保存需要插入的值
            int k=i-1;//保存需要插入的位置
            while(k>=0 && arr[k]>end){//寻找需要插入的位置
                arr[k+1]=arr[k];
                k--;
            }
            arr[k+1]=end;//将元素是插入到指定的位置
        }
    }

5.时间复杂度，空间复杂度及稳定性

（1）时间复杂度：O(N^2)

 （2）空间复杂度：O(1)

执行过程中没有借助辅助空间。

（3）什么是稳定性

（4）稳定性：稳定       

6.应用场景

适合于基本有序的数组或者数据量特别小的数组，因为基本有序，那么中间进行比较的次数就会减少。

二.希尔排序

1.引言

如果需要排序的数字量特别多而且比较凌乱，而且还需要使用插入排序，这时候就有了希尔排序。

2.希尔排序思想

先选定一个合适的距离，然后以该距离为分割长度，依次对该距离的所有元素进行插入排序，然后再缩小这个距离，直到距离为1时结束。

3.希尔排序动图

 

4.希尔排序思路图解

这里每次对于gap间距的值为gap=gap/3+1来处理

 5.代码实现

 public static void shellSort(int[] arr){
        int gap=arr.length;
        while(gap>1){
            gap= gap/3+1;
           for(int i=gap;i<arr.length;i++){
                int end=arr[i];
                int k=i-gap;
                while(k>=0 && arr[k]>end){
                    arr[k+gap]=arr[k];
                    k-=gap;
                }
                arr[k+gap]=end;
           }
        }

    }

 6.时间复杂度，空间复杂度及稳定性分析

（1）时间复杂度

如果gap选取的不同，则时间复杂度就，对于希尔排序，时间复杂度没有一个确定的值，当前增量法的时间复杂度大致为O(N^1.25)到O(1.6N^1.25)之间。

（2）空间复杂度        

        O(1)

（3）稳定性分析

由于每次都时间隔排序，所以不稳定

7.应用场景

对于数据量特别大，数字比较凌乱的情况下，而且还需要使用插入排序的情况下,可以使用希尔排序来进行处理。

三.选择排序（升序）

1.排序思想

每次选择一个最大的数放在数组的末尾（或者每次选择一个最下的放在数组头，起始位置后移），然后数组长度-1，接着使用该方法，直到所有的元素排序完成即可。

2.选择排序动态图示

3.思路图解

 4.代码实现

    //选择排序（每次选最大的元素放在数组末尾）
    public static void selectSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            int maxVal=0;
            for(int j=1;j<arr.length-i;j++){
                if(arr[maxVal]<arr[j]){
                    maxVal=j;
                }
            }
            if(maxVal!=arr.length-i)
            swap(arr,maxVal,arr.length-1-i);
        }
    }
    public static void swap(int[] arr,int left,int right){
        int tmp=arr[left];
        arr[left]=arr[right];
        arr[right]=tmp;
    }

5.时间复杂度，空间复杂度及稳定性分析

（1）时间复杂度

每一个元素都与前n-i-1个元素进行比较，所以时间复杂度为O(N^2)

（2）空间复杂度

没有额外空间的开辟，所以空间复杂度为O(1)

（3）稳定性

由于每次都是间隔进行交换，所以相同的元素最后位置可能会改变，所以不稳定。

6.应用场景

由于时间复杂度不好，平时应应用的比较少。

四.堆排序

1.堆排序的排序思想

堆排序)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.堆排序动图演示

 

 3.思路图解及代码实现

认识优先级队列与堆_小白 菜的博客-CSDN博客

4.时间复杂度，空间复杂度及稳定性

（1）时间复杂度

因为堆排序相当于删除元素，所以删除需要N次，然后每次向下调整最坏为二叉树的层数为,

所以时间复杂度为O(N*)

（2）空间复杂度

        O(1)

（3）稳定性

 由于间隔进行交换，所以不稳定。

5.应用场景

需要前k个最大或最小元素时，或者与其他排序一块使用

五.冒泡排序

1.排序思想

大的元素向下沉，小的元素向上浮。

2.冒泡排序动图演示

3.冒泡排序图解

4.冒泡排序代码：

    //冒泡排序
    public static void bubbleSort(int[] arr){
        //冒泡的趟数
        for(int i=0;i<arr.length-1;i++){
            boolean flag = false;//判断是否交换
            //在子区间进行冒泡
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);//交换2个元素
                    flag=true;
                }
            }
            //没有再进行交换则退出
            if(!flag){
                return;
            }
        }
    }
   public static void swap(int[] arr,int left,int right){
        int tmp=arr[left];
        arr[left]=arr[right];
        arr[right]=tmp;
    }

 5.时间复杂度，空间复杂度及稳定性

（1）时间复杂度

O(N^2)

（2）空间复杂度

O(1)

（3）稳定性

没有间隔进行交换，所以稳定

6.应用场景

基本不使用

六.快速排序

1.快速排序思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

原理：以基准值为中心，将区间划分为左边的值都小于基准值，右边的值都大于基准值，直到所有元素有序即可。

2.快速排序动图演示

 3.思路图解

 

 

 4.代码实现

如果递归深度过深，我们可以对递归到小区间的时候使用插入排序，这样可以提高排序速度，这样也是对快排进行优化。

//使用三数取中法选择合适基准值，对快排优化
    public static int midDiv(int[] arr,int left,int right){
        int mid = left+(right-left)>>1;
        //在左右值比较后然后中间值与左右进行比较
        if(arr[left]<arr[right-1]){//左小右大
            if(arr[mid]<arr[left]){
                return left;
            }else if(arr[mid]>arr[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }else {//左大右小
            if(arr[mid]<arr[right-1]){
                return right-1;
            }else if(arr[mid]>arr[left]){
                return left;
            }else {
                return mid;
            }
        }

    }

//前后指针法，划分区间，得到基准值
    public static int partiton(int[] arr,int left,int right){
        int prev=left-1;
        int cur = left;
        int midDiv=midDiv(arr,left,right);//找合适基准值的位置
        swap(arr,midDiv,right-1);//基准值位置与最后元素交换
        int div = arr[right-1];
        while(cur<right){
           if(arr[cur]<div && ++prev !=cur){
               //交换
               swap(arr,prev,cur);
           }
           cur++;
        }
        if(++prev!=right-1)
        swap(arr,prev,right-1);
        return prev;
    }
//快速排序(递归版)
    public static void quickSort(int[] arr,int left,int right){
            //剩一个元素排序结束
            if(right-left>1){
                int div = partiton(arr,left,right);//找基准值划分区间
                //左[left,val)
                quickSort(arr,left,div);
                //右[val+1,right)
                quickSort(arr,div+1,right);
            }

5.时间复杂度，空间复杂度及稳定性分析

（1）时间复杂度

注意：对于未选择三数取中的方法时，最坏的时间复杂度为O(N^2)，这是因为可能每次划分的时候左边的都比最后一个小，相当于每次只能排好一个，每一个需要的时间大概为N,共有N个元素，所以为O(N^2)，但是当每次最后一个数都为中间值的时候，时间复杂度就变为O(*N)，为递归的深度。

通过优化后最终得到的时间复杂度为O(*N)

（2）空间复杂度

在递归的时候借助了辅助空间，空间复杂度为递归的深度，所以空间复杂度为O()。

（3）稳定性

间隔进行了交换，所以不稳定。

6.应用场景

在数据特别随机的时候使用快排比较高效

七.归并排序

1.归并思想

该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.归并排序动图演示

 3.实现归并的思路图解

·

 

 

4.代码实现

public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(right-left>1){
            int mid = left+((right-left)>>1);//注意优先级问题，否则会出现栈溢出
            //分区间
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid,right,temp);
            //（合区间）将划分好的区间进行有序合并
            mergeData(arr,left,mid,right,temp);
            //将合并好的区间拷贝的原数组中
            System.arraycopy(temp,left,arr,left,right-left);
        }

    }
    //负责将划分好的区间进行合并
    public static void mergeData(int[] arr,int left,int mid,int right,int[] temp){
        int leftT=left;
        int midT = mid;
        int index=left;
        while(leftT<mid && midT<right){
            if(arr[leftT]<=arr[midT]){
                temp[index++]=arr[leftT++];
            }else {
                temp[index++]=arr[midT++];
            }
        }
        while(leftT<mid){
            temp[index++]=arr[leftT++];
        }
        while(midT<right){
            temp[index++]=arr[midT++];
        }
    }

5.时间复杂度，空间复杂度及稳定性分析

（1）时间复杂度

O(*N)

（2）空间复杂度

这里分析空间复杂度的时候不能按照递归深度*合并次数来进行计算，因为每次递归合并后，就将之前的空间释放掉了，所以借助的空间只有之前的辅助空间用来存储合并有序的数，最终空间复杂度为O(N)

（3）稳定性

在进行归并的时候没有间隔，所以稳定。

6.应用场景

应用于外部排序。

八.计数排序

1.排序思想

统计相同元素出现的次数，然后根据统计的次数回收到原来的数组中即可。

2.应用场景

对于数据特别集中在某个范围内时，效率是很高的。

3，思路图解

 

 4.代码实现

   public static void countSort(int[] arr){
        int size=arr.length;
        if(size==0){
            return;
        }
        int max=arr[0];
        int min=arr[0];
        //获取最大最小值
        for(int i=1;i<size;i++){
            if(arr[i]>max){
                max=arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        //这里数组的大小为max-min+1，直接使用max-min会出现数组越界
        int[] tmp = new int[max-min+1];
        //将每一个值出现的次数保存到对应的位置即可
        for(int i=0;i<size;i++){
            tmp[arr[i]-min]++;
        }
        int index=0;
        //将结果进行还原
        for(int i=0;i<tmp.length;i++){
            for(int j=0;j<tmp[i];j++){
                arr[index++]=min+i;
            }
        }
    }

5.时间复杂度，空间复杂度及稳定性

（1）时间复杂度

时间复杂度为：O(N)，为元素的个数

（2）空间复杂度

空间复杂度为：O(Max-Min)

（3）稳定性

没有间隔交换稳定

6.应用场景

对于数字比较集中在某个区间范围内时排序效率比较高。