第Java中七種排序算法總結分析目錄前言：對文章出現(xiàn)的一些名詞進行解釋一、插入排序1.基本思想2.直接插入排序3.希爾排序(縮小增量排序)二、選擇排序1.基本思想2.直接選擇排序3.堆排序三、交換排序1.基本思想2.冒泡排序3.快速排序（遞歸與非遞歸）1.Hoare版

2.挖坑法

3.前后標記法（難理解）

4.快速排序優(yōu)化

5.快速排序非遞歸

6.相關特性總結四、歸并排序（遞歸與非遞歸）

前言：對文章出現(xiàn)的一些名詞進行解釋

排序：使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或者遞減排列起來的操作。

穩(wěn)定性：假定在排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，a=b，且a在b之前，而在排序后的序列中，a仍然在b之前則這種排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

文中所有排序都是升序。

一、插入排序

直接插入排序是一種簡單的插入排序法。

1.基本思想

把待排序的記錄按照其關鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有記錄全部插完為止，得到一個新的有序序列。這種思想在我們玩撲克牌的時候用到過，在我們碼牌時，抽出一個牌，會從后往前依次比較牌面值，然后插入到一個比前面大且比后面小的位置中。

2.直接插入排序

步驟：

1.第一次排序先將第一個元素看成是已排序區(qū)間，將其內(nèi)容保存起來

2.待排序區(qū)間是其后面的所有元素，從其后面第一個開始，依次和已排序區(qū)間里的元素比較（這里的比較是從后向前比較，也就是從其前一個元素比較到0號位置的元素）

3.如果小于已排序區(qū)間中的元素，則將該位置向后挪一位

4.直到找到第一個比其小的元素，此時其后面的所有元素都是比它大的，且都向后挪了一位，這時其后面的位置是空的，將該元素放進來即可。

5.之后取第二個，第三個…第i個依次這樣比較即可，即循環(huán)起來。其中每次[0,i)是已排序區(qū)間，[i,size)是待排序區(qū)間。

動圖演示：

代碼實現(xiàn)：

publicstaticvoidinsertSort(int[]array){

intj=0;

//i位置與之前所有下標從后往前進行比較，該位置大于i則繼續(xù)往前，小于則插入到后邊

//[0,bound)已排序區(qū)間

//[bound,size)待排序區(qū)間

for(intbound=1;boundarray.length;bound++){

inttemp=array[bound];

//先取已排序區(qū)間的最后一個，依次往前進行比較

for(j=bound-1;jj--){

//如果temp小于，則將元素往后移一位

if(array[j]temp){

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

}else{

break;

//找到合適位置，填充

array[j+1]=temp;

相關特性總結：

時間復雜度：O(N2)

空間復雜度：O(1)

穩(wěn)定性：穩(wěn)定（是從后往前依次比較的）

應用場景：元素越接近有序越好（因為越接近有序比較次數(shù)就會越少，算法的時間效率就會越高）

3.希爾排序(縮小增量排序)

基本思想：

把待排序區(qū)間中所有記錄分成幾個組，設置一個gap值，所有距離為gap的記錄分在同一組內(nèi)，并分別對每個組內(nèi)的記錄進行排序，然后讓gap以一定的規(guī)律減小，然后重復上述分組和排序的工作，當gap達到1時，所有記錄已經(jīng)排好序。

步驟：

1.設置gap值（每個組內(nèi)元素之間間隔）

2.在每個組內(nèi)進行直接插入排序

3.縮小gap值（這里我按照2倍縮?。?/p>

4.gap為1時排序完畢

圖象解釋：

代碼實現(xiàn)：

publicstaticvoidshellSort(int[]array){

intgap=array.length/2;

while(gap0){

intj=0;

//i位置與之前所有下標從后往前進行比較，該位置大于i則繼續(xù)往前，小于則插入到后邊

for(intbound=gap;boundarray.length;bound+=gap){

inttemp=array[bound];

for(j=bound-gap;jj-=gap){

if(array[j]temp){

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

}else{

break;

array[j+gap]=temp;

gap=gap/2;

相關特性總結：

希爾排序是對直接插入排序的優(yōu)化

當gap1時都是預排序，目的是讓數(shù)組更接近有序，當gap==1時，數(shù)組已經(jīng)接近有序，這樣就很會快，整體而言，可以達到優(yōu)化的效果

時間復雜度不確定，因為gap取值方法有很多

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定（元素之間是跳著交換的）

二、選擇排序

1.基本思想

每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。

2.直接選擇排序

步驟：

1.先記錄下標為0元素為最小值

2.從下標為1開始往后遍歷，遇到比最小值還小的就標記起來，遍歷完成即找到最小值

3.將找到的最小值與下標為0的元素進行交換

4.此時[0,1）為已排序區(qū)間，即不再動，[1,size)是待排序區(qū)間

5.從下標為1繼續(xù)上面的操作，即循環(huán)起來

6.循環(huán)到最后只剩一個元素結束，排序完成

動圖演示：

代碼實現(xiàn)：

publicstaticvoidselectSort(int[]nums){

//每次都和第一個元素相比，如果小于則和一個元素則交換

for(intbound=0;boundnums.length-1;bound++){

//先記錄最小值為第一個元素

intmin=bound;

//從其后一個開始遍歷，找出后面所有元素中的最小值

for(inti=bound+1;inums.length;i++){

if(nums[min]nums[i]){

min=i;

//將最小值與待排序區(qū)間第一個進行交換

swap(nums,bound,min);

相關特性總結：

時間復雜度：O(N2)

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

效率不是很好，實際中很少使用

3.堆排序

堆排序是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。

注意：排升序要建大堆，排降序要建小堆

步驟：

1.創(chuàng)建一個大堆（升序）

從倒數(shù)第一個非葉子結點開始向下調(diào)整，直到根結點，創(chuàng)建一個大堆

2.將根結點與最后一個結點進行交換，此時最后一個元素一定是所有元素中最大的

3.將size–

4.將堆繼續(xù)調(diào)整好形成一個大堆，繼續(xù)上面的操作，即循環(huán)起來

5.最終排序完成

圖像解釋：

代碼實現(xiàn)：

//寫一個交換函數(shù)

privatestaticvoidswap(int[]array,intparent,intchild){

inttemp=array[child];

array[child]=array[parent];

array[parent]=temp;

//排升序建大堆

//向下調(diào)整，上篇博客提到了

privatestaticvoidshiftDown(int[]array,intparent,intsize){

intchild=parent*2+1;

while(childsize){

if(child+1sizearray[child+1]array[child]){

child+=1;

if(array[parent]array[child]){

swap(array,parent,child);

parent=child;

child=parent*2+1;

}else{

return;

//堆排序

publicstaticvoidheapSort(int[]array){

//創(chuàng)建一個堆

intsize=array.length;

for(introot=(size-2)/2;rootroot--){

shiftDown(array,root,size);

while(size1){

//將第一個和最后一個元素進行交換

swap(array,0,size-1);

//交換完成向下調(diào)整

size--;

shiftDown(array,0,size);

相關特性總結：

時間復雜度：O(NlogN)

空間復雜度：O(1)

穩(wěn)定性：不穩(wěn)定

使用堆來選數(shù)，效率高了很多

三、交換排序

1.基本思想

交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來兌換這兩個記錄在序列中的位置，交換序列的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的頭部移動

2.冒泡排序

步驟：

1.從0號位置開始，將元素和他后面的元素比較，如果大于則交換

2.當遍歷完成，最大的元素肯定在數(shù)組的最后

3.之后再比較時，最后一個元素就是已排序區(qū)間，不再參與比較

4.重復上述步驟，即循環(huán)起來

動圖演示：

代碼實現(xiàn)：

publicstaticvoidbubbleSort(int[]nums){

//外層循環(huán)控制循環(huán)次數(shù)

for(intnum=1;numnums.length;num++){

//內(nèi)層循環(huán)控制交換哪兩個元素

for(inti=0;inums.length-num;i++){

if(nums[i+1]nums[i]){

swap(nums,i+1,i);

相關特性總結：

時間復雜度：O(N2)

空間復雜度：O(1)

穩(wěn)定性：穩(wěn)定

冒泡排序在最開始就已經(jīng)學到，很容易理解

3.快速排序（遞歸與非遞歸）

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右子序列重復該過程，直到所有元素都排列在相應的位置上為止。

主框架實現(xiàn)：

publicstaticvoidquickSort(int[]array,intleft,intright){

if((right-left)=1){

return;

//按照基準值對array數(shù)組的[left,right)區(qū)間中的元素進行劃分

intdiv=partition3(array,left,right);

//劃分成功后以div為邊界形成了左右兩部分[left,div)和[div+1,right)

//遞歸排[left,div)

quickSort(array,left,div);

//遞歸排[div+1,right)

quickSort(array,div+1,right);

從上述程序可以看出，程序結構與二叉樹前序遍歷規(guī)則非常像。

接下來按照基準值劃分就是快排的核心，常見方法有三種：

1.Hoare版

步驟：

1.這里我們?nèi)∽钣覀葹榛鶞手?/p>

2.設置begin和end用來標記，讓begin從左往右走，end從右往左走

3.當begin小于end時，因為我們?nèi)〉没鶞手禐樽钣覀?，所以應先讓begin從左往右走，找到比基準值大的元素就停下來

4.這時讓end從右往左走，找到比基準值小的元素就停下來，兩者交換位置

5.循環(huán)起來

6.當循環(huán)結束時，兩個最終走到了同一個位置，將其和基準值進行交換

動圖演示：

代碼實現(xiàn)：

privatestaticintpartition1(int[]array,intleft,intright){

inttemp=array[right-1];

//begin從左往右找

intbegin=left;

//end從右往左找

intend=right-1;

while(beginend){

//讓begin從前往后找比temp大的元素，找到之后停下來

while(array[begin]=tempbeginend){

begin++;

//讓end從后往前找比temp小的元素，找到之后停下來

while(array[end]=tempbeginend){

end--;

//當兩個在同一個位置時，不需要交換，減少交換次數(shù)

if(begin!=end){

swap(array,begin,end);

if(begin!=right-1){

swap(array,begin,right-1);

returnbegin;

2.挖坑法

步驟：

1.先將基準值（這里是最右側元素）放在臨時變量temp中，這里就形成第一個坑位

2.設置begin和end用來標記，讓begin從左往右走，end從右往左走

3.當begin小于end時，讓begin從左往右走，找到比temp大的值，去填end的坑，同時begin這里形成一個坑位

4.然后讓end從右往左走，找到比temp小的值，去填begin的坑，同時end這里形成了一個新的坑位

5.就這樣一直循環(huán)，互相填坑，直到不滿足循環(huán)條件

6.這時begin和end在同一個坑位，且是最后一個坑位，使用基準值填充

圖象解釋：

代碼實現(xiàn)：

privatestaticintpartition2(int[]array,intleft,intright){

inttemp=array[right-1];

intbegin=left;

intend=right-1;

while(beginend){

//讓begin從前往后找比基準值大的元素

while(array[begin]=tempbeginend){

begin++;

if(begin!=end){

//begin位置找到了一個比temp大的元素，填end的坑

array[end]=array[begin];

//begin位置形成了一個新的坑位

//讓end從后往前找比基準值小的元素

while(array[end]=tempbeginend){

end--;

if(begin!=end){

//end位置找到了一個比temp小的元素，填begin的坑

array[begin]=array[end];

//end位置形成了一個新的坑位

//begin和end位置是最后的一個坑位

//這個坑位使用基準值填充

array[begin]=temp;

returnbegin;

3.前后標記法（難理解）

小編其實也是根據(jù)大佬的代碼分析出來的，要問為什么這么做咱確實也是不太理解，另外如理解錯誤歡迎指正

這里真誠發(fā)問，大佬們的腦子是不是和我的腦子不太一樣？

步驟：

1.采用cur和prev來標記，兩者都是從左往右走，不一樣的是，最開始cur在0號位置，prev在cur前一個位置上

2.當遇到比temp大的元素時，prev不動，cur向前走一步，當兩者一前一后的狀態(tài)時，cur也會往前走一步，而prev不動

3.這樣兩者逐漸拉開差距，此時遇到比基準值小的元素，cur中的元素就會與prev中的元素交換

4.走到最后prev的下一個元素與基準值位置交換

圖象解釋：

代碼實現(xiàn)：

privatestaticintpartition3(int[]array,intleft,intright){

inttemp=array[right-1];

intcur=left;

intprev=cur-1;

//讓cur從前往后找比基準值小的元素

while(curright){

if(array[cur]temp++prev!=cur){

swap(array,cur,prev);

cur++;

//將基準值的位置放置好

if(++prev!=right-1){

swap(array,prev,right-1);

returnprev;

但是會發(fā)現(xiàn)：

當我們選取的基準值越靠近整個數(shù)組的中間時，效率越好，這時可以看作是將數(shù)組逐漸分成了一個滿二叉樹，因此效率為O(NlogN)

最差時是取到其最大或者最小的元素，還是要劃分n次，效率為O(N2)

一般時間復雜度都是看起最差情況，那為什么快速排序的時間復雜度是O(NlogN)呢？

其實是可以對取基準值進行優(yōu)化的，詳情請看下面：

4.快速排序優(yōu)化

1.三數(shù)取中法選temp

之前我們只取一個基準值

優(yōu)化后，我們在左邊取一個，中間取一個，右邊取一個

比較三個數(shù)的大小，誰在中間就取誰為基準值

privatestaticintgetIndexOfMid(int[]array,intleft,intright){

intmid=left+((right-left)1);

if(array[left]array[right-1]){

if(array[mid]array[left]){

returnleft;

}elseif(array[mid]array[right-1]){

returnright-1;

}else{

returnmid;

在更改上面的劃分方法中，只需要看看上面取出的基準值在不在最右側，如果不在就與最右側的值交換，這樣代碼改動就比較小。

intindex=getIndexOfMid(array,left,right);

if(index!=right-1){

swap(array,index,right-1);

2.遞歸到小的子區(qū)間時，可以考慮使用插入排序

在Idea的內(nèi)層方法中，用的是小于47使用直接插入排序

5.快速排序非遞歸

如果直接轉為循環(huán)不好轉，之前提到可以使用棧來實現(xiàn)，利用棧后進先出的特性

publicstaticvoidquickSortNor(int[]array){

StackIntegers=newStack();

s.push(array.length);

s.push(0);

while(!s.empty()){

intleft=s.pop();

intright=s.pop();

if((right-left)47){

insertSortQuick(array,left,right);

}else{

intdiv=partition1(array,left,right);

//先壓入基準值的右半側

s.push(right);

s.push(div+1);

//再壓入基準值的左半側

s.push(div);

s.push(left);

6.相關特性總結

時間復雜度：O(NlogN)

空間復雜度：O(logN)(遞歸單次沒有借助輔助空間，高度即是深度)

穩(wěn)定性：不穩(wěn)定

快速排序整體綜合性能和使用場景都是比較好的，所以才叫快速排序

四、歸并排序（遞歸與非遞歸）

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

動圖演示：

歸并排序核心步驟：將兩個有序數(shù)組合并成一個有序數(shù)組

privatestaticvoidmergeData(int[]array,intleft,intmid,intright,int[]temp){

intbegin1=left,end1=mid;

intbegin2=mid,end2=right;

intindex=left;

while(begin1end1begin2end2){

//依次比較每一位上的元素，小的放入temp同時下標后移一位

if(array[begin1]array[begin2]){

temp[index++]=array[begin2++];

}else{

temp[index++]=array[begin1++];

//看兩個數(shù)組哪個還沒有遍歷完成，直接順次放入temp數(shù)組的后面

while(begin1end1){

temp[index++]=array[begin1++];

while(begin2end2){

temp[index++]=array[begin2++];

主程序（遞歸）：

步驟：

1.先對待排序區(qū)間進行均分為兩個

2.使用遞歸，直到均分為每個區(qū)間只剩下一個元素時，每兩個使用二路歸并

3.將兩個有序數(shù)組合并為一個有序數(shù)組，將結果保存在temp中

4.最終temp保存的就是排序完成的數(shù)組，再拷貝回原數(shù)組中

privat