5.時(shí)間復(fù)雜度，空間復(fù)雜度及穩(wěn)定性分析

（1）時(shí)間復(fù)雜度

每一個(gè)元素都與前n-i-1個(gè)元素進(jìn)行比較，所以時(shí)間復(fù)雜度為O(N^2)

（2）空間復(fù)雜度

沒有額外空間的開辟，所以空間復(fù)雜度為O(1)

（3）穩(wěn)定性

由于每次都是間隔進(jìn)行交換，所以相同的元素最后位置可能會(huì)改變，所以不穩(wěn)定。

6.應(yīng)用場(chǎng)景

由于時(shí)間復(fù)雜度不好，平時(shí)應(yīng)應(yīng)用的比較少。

四.堆排序

1.堆排序的排序思想

堆排序)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

2.堆排序動(dòng)圖演示

?

?3.思路圖解及代碼實(shí)現(xiàn)

認(rèn)識(shí)優(yōu)先級(jí)隊(duì)列與堆_小白 菜的博客-CSDN博客

4.時(shí)間復(fù)雜度，空間復(fù)雜度及穩(wěn)定性

（1）時(shí)間復(fù)雜度

因?yàn)槎雅判蛳喈?dāng)于刪除元素，所以刪除需要N次，然后每次向下調(diào)整最壞為二叉樹的層數(shù)為,

所以時(shí)間復(fù)雜度為O(N*)

（2）空間復(fù)雜度

????????O(1)

（3）穩(wěn)定性

?由于間隔進(jìn)行交換，所以不穩(wěn)定。

5.應(yīng)用場(chǎng)景

需要前k個(gè)最大或最小元素時(shí)，或者與其他排序一塊使用

五.冒泡排序

1.排序思想

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

2.冒泡排序動(dòng)圖演示

3.冒泡排序圖解

4.冒泡排序代碼：

    //冒泡排序    public static void bubbleSort(int[] arr){        //冒泡的趟數(shù)        for(int i=0;iarr[j+1]){                    swap(arr,j,j+1);//交換2個(gè)元素                    flag=true;                }            }            //沒有再進(jìn)行交換則退出            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.時(shí)間復(fù)雜度，空間復(fù)雜度及穩(wěn)定性

（1）時(shí)間復(fù)雜度

O(N^2)

（2）空間復(fù)雜度

O(1)

（3）穩(wěn)定性

沒有間隔進(jìn)行交換，所以穩(wěn)定

6.應(yīng)用場(chǎng)景

基本不使用

六.快速排序

1.快速排序思想

任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

原理：以基準(zhǔn)值為中心，將區(qū)間劃分為左邊的值都小于基準(zhǔn)值，右邊的值都大于基準(zhǔn)值，直到所有元素有序即可。

2.快速排序動(dòng)圖演示

?3.思路圖解

?

?

?4.代碼實(shí)現(xiàn)

如果遞歸深度過深，我們可以對(duì)遞歸到小區(qū)間的時(shí)候使用插入排序，這樣可以提高排序速度，這樣也是對(duì)快排進(jìn)行優(yōu)化。

//使用三數(shù)取中法選擇合適基準(zhǔn)值，對(duì)快排優(yōu)化    public static int midDiv(int[] arr,int left,int right){        int mid = left+(right-left)>>1;        //在左右值比較后然后中間值與左右進(jìn)行比較        if(arr[left]arr[right-1]){                return right-1;            }else{                return mid;            }        }else {//左大右小            if(arr[mid]arr[left]){                return left;            }else {                return mid;            }        }    }//前后指針法，劃分區(qū)間，得到基準(zhǔn)值    public static int partiton(int[] arr,int left,int right){        int prev=left-1;        int cur = left;        int midDiv=midDiv(arr,left,right);//找合適基準(zhǔn)值的位置        swap(arr,midDiv,right-1);//基準(zhǔn)值位置與最后元素交換        int div = arr[right-1];        while(cur1){                int div = partiton(arr,left,right);//找基準(zhǔn)值劃分區(qū)間                //左[left,val)                quickSort(arr,left,div);                //右[val+1,right)                quickSort(arr,div+1,right);            }

5.時(shí)間復(fù)雜度，空間復(fù)雜度及穩(wěn)定性分析

（1）時(shí)間復(fù)雜度

注意：對(duì)于未選擇三數(shù)取中的方法時(shí)，最壞的時(shí)間復(fù)雜度為O(N^2)，這是因?yàn)榭赡苊看蝿澐值臅r(shí)候左邊的都比最后一個(gè)小，相當(dāng)于每次只能排好一個(gè)，每一個(gè)需要的時(shí)間大概為N,共有N個(gè)元素，所以為O(N^2)，但是當(dāng)每次最后一個(gè)數(shù)都為中間值的時(shí)候，時(shí)間復(fù)雜度就變?yōu)镺(*N)，為遞歸的深度。

通過優(yōu)化后最終得到的時(shí)間復(fù)雜度為O(*N)

（2）空間復(fù)雜度

在遞歸的時(shí)候借助了輔助空間，空間復(fù)雜度為遞歸的深度，所以空間復(fù)雜度為O()。

（3）穩(wěn)定性

間隔進(jìn)行了交換，所以不穩(wěn)定。

6.應(yīng)用場(chǎng)景

在數(shù)據(jù)特別隨機(jī)的時(shí)候使用快排比較高效

七.歸并排序

1.歸并思想

該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

2.歸并排序動(dòng)圖演示

?3.實(shí)現(xiàn)歸并的思路圖解

·

?

?

4.代碼實(shí)現(xiàn)

public static void mergeSort(int[] arr,int left,int right,int[] temp){        if(right-left>1){            int mid = left+((right-left)>>1);//注意優(yōu)先級(jí)問題，否則會(huì)出現(xiàn)棧溢出            //分區(qū)間            mergeSort(arr,left,mid,temp);            mergeSort(arr,mid,right,temp);            //（合區(qū)間）將劃分好的區(qū)間進(jìn)行有序合并            mergeData(arr,left,mid,right,temp);            //將合并好的區(qū)間拷貝的原數(shù)組中            System.arraycopy(temp,left,arr,left,right-left);        }    }    //負(fù)責(zé)將劃分好的區(qū)間進(jìn)行合并    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]