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;iarr[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]){                return right-1;            }else{                return mid;            }        }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(cur1){                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

   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;imax){                max=arr[i];            }            if(arr[i]