幾種常見排序算法

\o"JavaEE知識庫"Java當中有以下幾種常見排序算法：插入排序（直接插入排序、鏈表插入排序、分段/二分/折半插入排序、希爾排序/縮小增量排序）、冒泡排序、快速排序、簡單選擇排序、歸并排序、二叉樹排序、基數排序等。（1）復雜度比較表1幾種常見排序算法的復雜度算法名稱平均情況最好情況最壞情況輔助空間直接插入排序O(n^2)O(n)O(n^2)O(1)希爾排序O(nlog2n)~

o(n^2)O(n^1.3)O(n^2)O(1)冒泡排序O(n^2)O(n)O(n^2)O(1)快速排序O(nlog2n)O(nlog2n)O(n^2)O(n)簡單選擇排序O(n^2)O(n^2)O(n^2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)

基數排序O(n)O(n)O(n)O(1)

什么是排序算法的穩(wěn)定性？

假設在待排序的記錄中，有若干個相同的元素，如果排序后它們的相對位置并沒有發(fā)生變化，則說明該排序是穩(wěn)定的。

（2）穩(wěn)定性比較插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的，選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的。（3）其他方面比較插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。當n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許時用桶排序。當n較大時，關鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當n較大時，關鍵字元素可能出現本身是有序的，對穩(wěn)定性有要求時，空間允許的情況下。宜用歸并排序。當n較大時，關鍵字元素可能出現本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序。=============================================================================

相關知識介紹（所有定義只為幫助讀者理解相關概念，并非嚴格定義）：

1、穩(wěn)定排序和非穩(wěn)定排序簡單地說就是所有相等的數經過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就

說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。

比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序后為a1,a2,a4,a3,a5，

則我們說這種排序是穩(wěn)定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,

a2,a3,a5就不是穩(wěn)定的了。2、內排序和外排序在排序過程中，所有需要排序的數都在內存，并在內存中調整它們的存儲順序，稱為內排序；

在排序過程中，只有部分數被調入內存，并借助內存調整數在外存中的存放順序排序方法稱為外排序。3、算法的時間復雜度和空間復雜度所謂算法的時間復雜度，是指執(zhí)行算法所需要的計算工作量。

一個算法的空間復雜度，一般是指執(zhí)行這個算法所需要的內存空間。

=============================================================================一、插入排序包括：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）。屬于穩(wěn)定排序的一種（通俗地講，就是兩個相等的數不會交換位置）。（a）直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合并成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大于a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大于a[2]，則繼續(xù)跳過，直到b[1]小于a數組中某一數據a[x]，則將a[x]~a[n]分別向后移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）優(yōu)點：穩(wěn)定，快；缺點：比較次數不一定，比較次數越少，插入點后的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。（b）分段插入排序已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合并成一個升序數列。先將數組a分成x等份（x<<n)，每等份有n/x個數據。將每一段的第一個數據先儲存在數組c中：c[1]、c[2]、……c[x]。運用插入排序處理數組b中的數據。插入時b先與c比較，確定了b在a中的哪一段之后，再到a中相應的段中插入b。隨著數據的插入，a中每一段的長度會有變化，所以在每次插入后，都要檢測一下每段數據的量的標準差s，當其大于某一值時，將a重新分段。在數據量特別巨大時，可在a中的每一段中分子段，b先和主段的首數據比較，再和子段的首數據比較，可提高速度。優(yōu)點：快，比較次數少；缺點：不適用于較少數據的排序，s的臨界值無法確切獲知，只能憑經驗取。（c）希爾排序/縮小增量排序由希爾在1959年提出，又稱希爾排序。已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發(fā)現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最后一組依此類推，在各組內用插入排序，然后取d'<d，重復上述操作，直到d=1。優(yōu)點：快，數據移動少；缺點：不穩(wěn)定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。

三、冒泡排序已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大于a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大于a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，依此類推，最后比較a[n-1]與a[n]的值。這樣處理一輪后，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，依此類推。共處理n-1輪后a[1]、a[2]、……a[n]就以升序排列了。優(yōu)點：穩(wěn)定，比較次數已知；缺點：慢，每次只能移動相鄰兩個數據，移動數據的次數多。四、快速排序=============================================================================設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。一趟快速排序的算法是：1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；5）重復第3、4步，直到i=j；

(3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i，

j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結束）。快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。即使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然后采用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。優(yōu)點：極快，數據移動少；缺點：不穩(wěn)定。編碼實現如下：

packagecom.quick;

publicclassquick{

publicvoidquick_sort(int[]arrays,intlenght){

if(null==arrays||lenght<1){

System.out.println("inputerror!");

return;

}

_quick_sort(arrays,0,lenght-1);

}

publicvoid_quick_sort(int[]arrays,intstart,intend){

if(start>=end){

return;

}

inti=start;

intj=end;

intvalue=arrays[i];

booleanflag=true;

while(i!=j){

if(flag){

if(value>arrays[j]){

swap(arrays,i,j);

flag=false;

}else{

j--;

}

}else{

if(value<arrays[i]){

swap(arrays,i,j);

flag=true;

}else{

i++;

}

}

}

snp(arrays);

_quick_sort(arrays,start,j-1);

_quick_sort(arrays,i+1,end);

}

publicvoidsnp(int[]arrays){

for(inti=0;i<arrays.length;i++){

System.out.print(arrays[i]+"");

}

System.out.println();

}

privatevoidswap(int[]arrays,inti,intj){

inttemp;

temp=arrays[i];

arrays[i]=arrays[j];

arrays[j]=temp;

}

publicstaticvoidmain(Stringargs[]){

quickq=newquick();

int[]a={49,38,65,12,45,5};

q.quick_sort(a,6);

}

}=============================================================================Java123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127classQuick{publicvoidsort(intarr[],intlow,inthigh){intl=low;inth=high;intpovit=arr[low];

while(l<h){while(l<h&&arr[h]>=povit)h--;if(l<h){inttemp=arr[h];arr[h]=arr[l];arr[l]=temp;l++;}

while(l<h&&arr[l]<=povit)l++;

if(l<h){inttemp=arr[h];arr[h]=arr[l];arr[l]=temp;h--;}}print(arr);System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");if(l>low)sort(arr,low,l-1);if(h<high)sort(arr,l+1,high);}}

/*//////////////////////////方式二////////////////////////////////*/更高效點的代碼：public<TextendsComparable<?superT>>T[]quickSort(T[]targetArr,intstart,intend){inti=start+1,j=end;Tkey=targetArr[start];SortUtil<T>sUtil=newSortUtil<T>();

if(start>=end)return(targetArr);

/*從i++和j--兩個方向搜索不滿足條件的值并交換**條件為：i++方向小于key，j--方向大于key*/while(true){while(targetArr[j].compareTo(key)>0)j--;while(targetArr[i].compareTo(key)<0&&i<j)i++;if(i>=j)break;sUtil.swap(targetArr,i,j);if(targetArr[i]==key){j--;}else{i++;}}

/*關鍵數據放到‘中間’*/sUtil.swap(targetArr,start,j);

if(start<i-1){this.quickSort(targetArr,start,i-1);}if(j+1<end){this.quickSort(targetArr,j+1,end);}

returntargetArr;}

/*//////////////方式三：減少交換次數，提高效率/////////////////////*/private<TextendsComparable<?superT>>voidquickSort(T[]targetArr,intstart,intend){inti=start,j=end;Tkey=targetArr[start];

while(i<j){/*按j--方向遍歷目標數組，直到比key小的值為止*/while(j>i&&targetArr[j].compareTo(key)>=0){j--;}if(i<j){/*targetArr[i]已經保存在key中，可將后面的數填入*/targetArr[i]=targetArr[j];i++;}/*按i++方向遍歷目標數組，直到比key大的值為止*/while(i<j&&targetArr[i].compareTo(key)<=0)/*此處一定要小于等于零，假設數組之內有一億個1，0交替出現的話，而key的值又恰巧是1的話，那么這個小于等于的作用就會使下面的if語句少執(zhí)行一億次。*/{i++;}if(i<j){/*targetArr[j]已保存在targetArr[i]中，可將前面的值填入*/targetArr[j]=targetArr[i];j--;}}/*此時i==j*/targetArr[i]=key;

/*遞歸調用，把key前面的完成排序*/this.quickSort(targetArr,start,i-1);

/*遞歸調用，把key后面的完成排序*/this.quickSort(targetArr,j+1,end);

}=============================================================================五、選擇排序算法思想簡單描述：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；

然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環(huán)

到倒數第二個數和最后一個數比較為止。選擇排序是不穩(wěn)定的。算法復雜度O(n^2)優(yōu)點：穩(wěn)定，比較次數與冒泡排序一樣，數據移動次數比冒泡排序少；缺點：相對之下還是慢。=====================================================

*/

voidselect_sort(int*x,intn)

{

inti,j,min,t;for(i=0;i<n-1;i++)/*要選擇的次數：0~n-2共n-1次*/

{

min=i;/*假設當前下標為i的數最小，比較后再調整*/

for(j=i+1;j<n;j++)/*循環(huán)找出最小的數的下標是哪個*/

{

if(*(x+j)<*(x+min))

{

min=j;/*如果后面的數比前面的小，則記下它的下標*/

}

}

if(min!=i)/*如果min在循環(huán)中改變了，就需要交換數據*/

{

t=*(x+i);

*(x+i)=*(x+min);

*(x+min)=t;

}

}

}

/*

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

六、堆排序堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素。堆排序是不穩(wěn)定的排序方法，輔助空間為O(1)，最壞時間復雜度為O(nlog2n)

，堆排序的堆序的平均性能較接近于最壞性能。

堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關鍵字的記錄變得簡單。（1）用大根堆排序的基本思想①先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū)②再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key③由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆?！钡綗o序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作：

①初始化操作：將R[1..n]構造為初始堆；②每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調整為堆(亦稱重建堆)。注意：

①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。代碼實現：

[java]

\o"viewplain"viewplain

\o"copy"copy

\o"print"print\o"?"?public

class

HeapSortTest

{

public

static

void

main(String[]

args)

{

int[]

data5

=

new

int[]

{

5,

3,

6,

2,

1,

9,

4,

8,

7

};

print(data5);

heapSort(data5);

System.out.println("排序后的數組：");

print(data5);

}

public

static

void

swap(int[]

data,

int

i,

int

j)

{

if

(i

==

j)

{

return;

}

data[i]

=

data[i]

+

data[j];

data[j]

=

data[i]

-

data[j];

data[i]

=

data[i]

-

data[j];

}

public

static

void

heapSort(int[]

data)

{

for

(int

i

=

0;

i

<

data.length;

i++)

{

createMaxdHeap(data,

data.length

-

1

-

i);

swap(data,

0,

data.length

-

1

-

i);

print(data);

}

}

public

static

void

createMaxdHeap(int[]

data,

int

lastIndex)

{

for

(int

i

=

(lastIndex

-

1)

/

2;

i

>=

0;

i--)

{

//

保存當前正在判斷的節(jié)點

int

k

=

i;

//

若當前節(jié)點的子節(jié)點存在

while

(2

*

k

+

1

<=

lastIndex)

{

//

biggerIndex總是記錄較大節(jié)點的值,先賦值為當前判斷節(jié)點的左子節(jié)點

int

biggerIndex

=

2

*

k

+

1;

if

(biggerIndex

<

lastIndex)

{

//

若右子節(jié)點存在，否則此時biggerIndex應該等于

lastIndex

if

(data[biggerIndex]

<

data[biggerIndex

+

1])

{

//

若右子節(jié)點值比左子節(jié)點值大，則biggerIndex記錄的是右子節(jié)點的值

biggerIndex++;

}

}

if

(data[k]

<

data[biggerIndex])

{

//

若當前節(jié)點值比子節(jié)點最大值小，則交換2者得值，交換后將biggerIndex值賦值給k

swap(data,

k,

biggerIndex);

k

=

biggerIndex;

}

else

{

break;

}

}

}

}

public

static

void

print(int[]

data)

{

for

(int

i

=

0;

i

<

data.length;

i++)

{

System.out.print(data[i]

+

"\t");

}

System.out.println();

}

}

運行結果：[java]

\o"viewplain"viewplain

\o"copy"copy

\o"print"print\o"?"?5

3

6

2

1

9

4

8

7

3

8

6

7

1

5

4

2

9

2

7

6

3

1

5

4

8

9

4

3

6

2

1

5

7

8

9

4

3

5

2

1

6

7

8

9

1

3

4

2

5

6

7

8

9

2

3

1

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

排序后的數組：

1

2

3

4

5

6

7

8

9

整個排序過程圖解：（待有時間再補充...）

七、歸并排序歸并排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。歸并排序算法穩(wěn)定，數組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間復雜度為O(nlog(n))，算法不是自適應的，不需要對數據的隨機讀取。工作原理：1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列2、設定兩個指針，最初位置分別為兩個已經排序序列的起始位置3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置4、重復步驟3直到某一指針達到序列尾5、將另一序列剩下的所有元素直接復制到合并序列尾代碼實現：[java]

\o"viewplain"viewplain

\o"copy"copy

\o"print"print\o"?"?public

class

MergeSortTest

{

public

static

void

main(String[]

args)

{

int[]

data

=

new

int[]

{

5,

3,

6,

2,

1,

9,

4,

8,

7

};

print(data);

mergeSort(data);

System.out.println("排序后的數組：");

print(data);

}

public

static

void

mergeSort(int[]

data)

{

sort(data,

0,

data.length

-

1);

}

public

static

void

sort(int[]

data,

int

left,

int

right)

{

if

(left

>=

right)

return;

//

找出中間索引

int

center

=

(left

+

right)

/

2;

//

對左邊數組進行遞歸

sort(data,

left,

center);

//

對右邊數組進行遞歸

sort(data,

center

+

1,

right);

//

合并

merge(data,

left,

center,

right);

print(data);

}

/**

*

將兩個數組進行歸并，歸并前面2個數組已有序，歸并后依然有序

*

*

@param

data

*

數組對象

*

@param

left

*

左數組的第一個元素的索引

*

@param

center

*

左數組的最后一個元素的索引，center+1是右數組第一個元素的索引

*

@param

right

*

右數組最后一個元素的索引

*/

public

static

void

merge(int[]

data,

int

left,

int

center,

int

right)

{

//

臨時數組

int[]

tmpArr

=

new

int[data.length];

//

右數組第一個元素索引

int

mid

=

center

+

1;

//

third

記錄臨時數組的索引

int

third

=

left;

//

緩存左數組第一個元素的索引

int

tmp

=

left;

while

(left

<=

center

&&

mid

<=

right)

{

//

從兩個數組中取出最小的放入臨時數組

if

(data[lef