Java各種排序算法總結(jié)

排序是程序開發(fā)中一種非常常見的操作，對(duì)一組任意的數(shù)據(jù)元素（或記錄）經(jīng)過排序操作后，就可以把他們變成一組按關(guān)鍵字排序的有序隊(duì)列。對(duì)一個(gè)排序算法來說，一般從下面3個(gè)方面來衡量算法的優(yōu)劣：時(shí)間復(fù)雜度：它主要是分析關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)?？臻g復(fù)雜度：分析排序算法中需要多少輔助內(nèi)存。穩(wěn)定性：若兩個(gè)記錄A和B的關(guān)鍵字值相等，但是排序后A,B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的；反之，就是不穩(wěn)定的。就現(xiàn)有的排序算法來看，排序大致可分為內(nèi)部排序和外部排序。如果整個(gè)排序過程不需要借助外部存儲(chǔ)器（如磁盤等），所有排序操作都是在內(nèi)存中完成，這種排序就被稱為內(nèi)部排序。如果參與排序的數(shù)據(jù)元素非常多，數(shù)據(jù)量非常大，計(jì)算無法把整個(gè)排序過程放在內(nèi)存中完成，必須借助于外部存儲(chǔ)器（如磁盤），這種排序就被稱為外部排序。外部排序最常用算噶是多路歸并排序，即將原文件分解稱多個(gè)能夠一次性裝入內(nèi)存的部分，分別把每一部分調(diào)入內(nèi)存完成排序，接下來再對(duì)多個(gè)有序的子文件進(jìn)行歸并排序。就常用的內(nèi)部排序算法來說，可以分為以下幾類：選擇排序（直接選擇排序，堆排序）交換排序（冒泡排序，快速排序）插入排序（直接插入排序，折半插入排序，Shell排序）歸并排序桶式排序基數(shù)排序Java排序算法（二）：直接選擇排序直接選擇排序的基本操作就是每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完，它需要經(jīng)過n-1趟比較。算法不穩(wěn)定，O(1)的額外的空間，比較的時(shí)間復(fù)雜度為O(n^2)，交換的時(shí)間復(fù)雜度為O(n)，并不是自適應(yīng)的。在大多數(shù)情況下都不推薦使用。只有在希望減少交換次數(shù)的情況下可以用?；舅枷雗個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。②第1趟排序在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)?！鄣趇趟排序第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)。這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。算法實(shí)現(xiàn)\o"viewplain"viewplainpublic

class

SelectSortTest{public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);selectSort(data);print(data);}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

selectSort(int[]data){for

(int

i=

0;i<data.length-

1;i++){int

minIndex=i;

//記錄最小值的索引for

(int

j=i+

1;j<data.length;j++){if

(data[j]<data[minIndex]){minIndex=j;

//若后面的元素值小于最小值,將j賦值給minIndex}}if

(minIndex!=i){swap(data,i,minIndex);print(data);}}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}運(yùn)行結(jié)果：\o"viewplain"viewplain536219487136259487126359487123659487123459687123456987123456789123456789Java排序算法（三）：堆排序堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆排序是不穩(wěn)定的排序方法，輔助空間為O(1)，最壞時(shí)間復(fù)雜度為O(nlog2n)，堆排序的堆序的平均性能較接近于最壞性能。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。（1）用大根堆排序的基本思想①先將初始文件R[1..n]建成一個(gè)大根堆,此堆為初始的無序區(qū)②再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。……直到無序區(qū)只有一個(gè)元素為止。（2）大根堆排序算法的基本操作：①初始化操作：將R[1..n]構(gòu)造為初始堆；②每一趟排序的基本操作：將當(dāng)前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個(gè)記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。注意：①只需做n-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止。代碼實(shí)現(xiàn)：\o"viewplain"viewplain\o"copytoclipboard"copytoclipboardpublic

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("排序后的數(shù)組：");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--){//保存當(dāng)前正在判斷的節(jié)點(diǎn)int

k=i;//若當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)存在while

(2

*k+

1

<=lastIndex){//biggerIndex總是記錄較大節(jié)點(diǎn)的值,先賦值為當(dāng)前判斷節(jié)點(diǎn)的左子節(jié)點(diǎn)int

biggerIndex=

2

*k+

1;if

(biggerIndex<lastIndex){//若右子節(jié)點(diǎn)存在，否則此時(shí)biggerIndex應(yīng)該等于lastIndexif

(data[biggerIndex]<data[biggerIndex+

1]){//若右子節(jié)點(diǎn)值比左子節(jié)點(diǎn)值大，則biggerIndex記錄的是右子節(jié)點(diǎn)的值biggerIndex++;}}if

(data[k]<data[biggerIndex]){//若當(dāng)前節(jié)點(diǎn)值比子節(jié)點(diǎn)最大值小，則交換2者得值，交換后將biggerIndex值賦值給kswap(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();}}

運(yùn)行結(jié)果：\o"viewplain"viewplain\o"copytoclipboard"copytoclipboard5

3

6

2

1

9

4

8

73

8

6

7

1

5

4

2

92

7

6

3

1

5

4

8

94

3

6

2

1

5

7

8

94

3

5

2

1

6

7

8

91

3

4

2

5

6

7

8

92

3

1

4

5

6

7

8

91

2

3

4

5

6

7

8

91

2

3

4

5

6

7

8

91

2

3

4

5

6

7

8

9排序后的數(shù)組：1

2

3

4

5

6

7

8

9

整個(gè)排序過程圖解：（待有時(shí)間再補(bǔ)充...）Java排序算法（四）：冒泡排序冒泡排序是計(jì)算機(jī)的一種排序方法，它的時(shí)間復(fù)雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數(shù)為2），但是有兩個(gè)優(yōu)點(diǎn)：1.“編程復(fù)雜度”很低，很容易寫出代碼；2.具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對(duì)順序仍然保持到排序后的序列，而堆排序、快速排序均不具有穩(wěn)定性。不過，一路、二路歸并排序、不平衡二叉樹排序的速度均比冒泡排序快，且具有穩(wěn)定性，但速度不及堆排序、快速排序。冒泡排序是經(jīng)過n-1趟子排序完成的，第i趟子排序從第1個(gè)數(shù)至第n-i個(gè)數(shù)，若第i個(gè)數(shù)比后一個(gè)數(shù)大（則升序，小則降序）則交換兩數(shù)。冒泡排序算法穩(wěn)定，O(1)的額外的空間，比較和交換的時(shí)間復(fù)雜度都是O(n^2)，自適應(yīng)，對(duì)于已基本排序的算法，時(shí)間復(fù)雜度為O(n)。冒泡算法的許多性質(zhì)和插入算法相似，但對(duì)于系統(tǒng)開銷高一點(diǎn)點(diǎn)。排序過程設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。代碼實(shí)現(xiàn)\o"viewplain"viewplainpublic

class

BubbleSortTest{public

static

void

main(String[]args){int[]data5=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7};print(data5);bubbleSort(data5);System.out.println("排序后的數(shù)組：");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

bubbleSort(int[]data){for

(int

i=

0;i<data.length-

1;i++){//記錄某趟是否發(fā)生交換，若為false表示數(shù)組已處于有序狀態(tài)boolean

isSorted=

false;for

(int

j=

0;j<data.length-i-

1;j++){if

(data[j]>data[j+

1]){swap(data,j,j+

1);isSorted=

true;print(data);}}if

(!isSorted){//若數(shù)組已處于有序狀態(tài)，結(jié)束循環(huán)break;}}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}

運(yùn)行結(jié)果\o"viewplain"viewplain5

3

6

2

1

9

4

8

73

5

6

2

1

9

4

8

73

5

2

6

1

9

4

8

73

5

2

1

6

9

4

8

73

5

2

1

6

4

9

8

73

5

2

1

6

4

8

9

73

5

2

1

6

4

8

7

93

2

5

1

6

4

8

7

93

2

1

5

6

4

8

7

93

2

1

5

4

6

8

7

93

2

1

5

4

6

7

8

92

3

1

5

4

6

7

8

92

1

3

5

4

6

7

8

92

1

3

4

5

6

7

8

91

2

3

4

5

6

7

8

9排序后的數(shù)組：1

2

3

4

5

6

7

8

9Java排序算法（五）：快速排序快速排序是一個(gè)速度非?？斓慕粨Q排序算法，它的基本思路很簡(jiǎn)單，從待排的數(shù)據(jù)序列中任取一個(gè)數(shù)據(jù)（如第一個(gè)數(shù)據(jù)）作為分界值，所有比它小的數(shù)據(jù)元素放到左邊，所有比它大的數(shù)據(jù)元素放到它的右邊。經(jīng)過這樣一趟下來，該序列形成左右兩個(gè)子序列，左邊序列中的數(shù)據(jù)元素的值都比分界值小，右邊序列中數(shù)據(jù)元素的值都比分界值大。

接下來對(duì)左右兩個(gè)子序列進(jìn)行遞歸排序，對(duì)兩個(gè)子序列重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)元素子表的元素只剩下一個(gè)元素，排序完成。思路：

1.定義一個(gè)i變量，i變量從左邊第一個(gè)索引開始，找大于分界值的元素的索引，并用i來記錄它。

2.定義一個(gè)j變量，j變量從右邊第一個(gè)索引開始，找小于分界值的元素的索引，并用j來記錄它。

3.如果i<j，交換i,j兩個(gè)索引處的元素。

重復(fù)執(zhí)行以上1,2,3步，直到i>=j，可以判斷j左邊的數(shù)據(jù)元素都小于分界值，j右邊的數(shù)據(jù)元素都大于分界值，最后將分界值和j索引處的元素交換即可。時(shí)間復(fù)雜度

最好情況（每次總是選到中間值作樞軸）T(n)=O(nlogn)

最壞情況（每次總是選到最小或最大元素作樞軸）

做n-1趟，每趟比較n-i次，總的比較次數(shù)最大：[O(n2)]

平均時(shí)間復(fù)雜度為：：T(n)=O(nlogn)代碼實(shí)現(xiàn)：\o"viewplain"viewplainpackage

sort;public

class

QuickSortTest{public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);quickSort(data,

0,data.length-

1);System.out.println("排序后的數(shù)組：");print(data);}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

quickSort(int[]data,

int

start,

int

end){if

(start>=end)return;//以起始索引為分界點(diǎn)int

pivot=data[start];int

i=start+

1;int

j=end;while

(true){while

(i<=end&&data[i]<pivot){i++;}while

(j>start&&data[j]>pivot){j--;}if

(i<j){swap(data,i,j);}

else

{break;}}//交換j和分界點(diǎn)的值swap(data,start,j);print(data);//遞歸左子序列quickSort(data,start,j-

1);//遞歸右子序列quickSort(data,j+

1,end);}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}

運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

71

3

4

2

5

9

6

8

71

3

4

2

5

9

6

8

71

2

3

4

5

9

6

8

71

2

3

4

5

7

6

8

91

2

3

4

5

6

7

8

9排序后的數(shù)組：1

2

3

4

5

6

7

8

9Java排序算法（六）：直接插入排序直接插入排序的基本操作就是將待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到前面的有序序列中。直接插入的時(shí)間效率并不高，如果在最壞的情況下，所有元素的比較次數(shù)總和為（0+1+...+n-1）=O(n^2)。其他情況下也要考慮移動(dòng)元素的次數(shù)，故時(shí)間復(fù)雜度為O(n^2)直接插入空間效率很好，只需要1個(gè)緩存數(shù)據(jù)單元，也就是說空間復(fù)雜度為O(1).直接插入排序是穩(wěn)定的。直接插入排序在數(shù)據(jù)已有一定順序的情況下，效率較好。但如果數(shù)據(jù)無規(guī)則，則需要移動(dòng)大量的數(shù)據(jù)，其效率就與冒泡排序法和選擇排序法一樣差了。算法描述對(duì)一個(gè)有n個(gè)元素的數(shù)據(jù)序列，排序需要進(jìn)行n-1趟插入操作：第1趟插入，將第2個(gè)元素插入前面的有序子序列--此時(shí)前面只有一個(gè)元素，當(dāng)然是有序的。第2趟插入，將第3個(gè)元素插入前面的有序子序列，前面2個(gè)元素是有序的。第n-1趟插入，將第n個(gè)元素插入前面的有序子序列，前面n-1個(gè)元素是有序的。代碼實(shí)現(xiàn)\o"viewplain"viewplainpackage

sort;public

class

InsertSortTest{public

static

int

count=

0;public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);insertSort(data);print(data);}public

static

void

insertSort(int[]data){for

(int

i=

1;i<data.length;i++){//緩存i處的元素值int

tmp=data[i];if

(data[i]<data[i-

1]){int

j=i-

1;//整體后移一格while

(j>=

0

&&data[j]>tmp){data[j+

1]=data[j];j--;}//最后將tmp插入合適的位置data[j+

1]=tmp;print(data);}}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}

運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

73

5

6

2

1

9

4

8

72

3

5

6

1

9

4

8

71

2

3

5

6

9

4

8

71

2

3

4

5

6

9

8

71

2

3

4

5

6

8

9

71

2

3

4

5

6

7

8

91

2

3

4

5

6

7

8

9\o"Java排序算法（七）：折半插入排序"Java排序算法（七）：折半插入排序分類：

JavaSE

Java排序2011-07-0621:10

81人閱讀

評(píng)論(2)

\o"收藏"收藏

\o"舉報(bào)"舉報(bào)Java排序算法（七）：折半插入排序折半插入排序法，又稱二分插入排序法，是直接插入排序法的改良版，也需要執(zhí)行i-1趟插入，不同之處在于，第i趟插入，先找出第i+1個(gè)元素應(yīng)該插入的的位置，假定前i個(gè)數(shù)據(jù)是已經(jīng)處于有序狀態(tài)。代碼實(shí)現(xiàn)：\o"viewplain"viewplainpackage

sort;public

class

BinaryInsertSortTest{public

static

int

count=

0;public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);binaryInsertSort(data);print(data);}public

static

void

binaryInsertSort(int[]data){for

(int

i=

1;i<data.length;i++){if

(data[i]<data[i-

1]){//緩存i處的元素值int

tmp=data[i];//記錄搜索范圍的左邊界int

low=

0;//記錄搜索范圍的右邊界int

high=i-

1;while

(low<=high){//記錄中間位置int

mid=(low+high)/

2;//比較中間位置數(shù)據(jù)和i處數(shù)據(jù)大小，以縮小搜索范圍if

(data[mid]<tmp){low=mid+

1;}

else

{high=mid-

1;}}//將low~i處數(shù)據(jù)整體向后移動(dòng)1位for

(int

j=i;j>low;j--){data[j]=data[j-

1];}data[low]=tmp;print(data);}}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

73

5

6

2

1

9

4

8

72

3

5

6

1

9

4

8

71

2

3

5

6

9

4

8

71

2

3

4

5

6

9

8

71

2

3

4

5

6

8

9

71

2

3

4

5

6

7

8

91

2

3

4

5

6

7

8

9Java排序算法（八）：希爾排序(Shell排序)希爾排序(縮小增量法)屬于插入類排序,由Shell提出，希爾排序?qū)χ苯硬迦肱判蜻M(jìn)行了簡(jiǎn)單的改進(jìn)：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進(jìn)行插入排序，從而使數(shù)據(jù)項(xiàng)大跨度地移動(dòng)，當(dāng)這些數(shù)據(jù)項(xiàng)排過一趟序之后，希爾排序算法減小數(shù)據(jù)項(xiàng)的間隔再進(jìn)行排序，依次進(jìn)行下去，進(jìn)行這些排序時(shí)的數(shù)據(jù)項(xiàng)之間的間隔被稱為增量，習(xí)慣上用字母h來表示這個(gè)增量。常用的h序列由Knuth提出，該序列從1開始，通過如下公式產(chǎn)生：h=3*h+1反過來程序需要反向計(jì)算h序列，應(yīng)該使用h=(h-1)/3代碼實(shí)現(xiàn)：\o"viewplain"viewplainpackage

sort;public

class

ShellSortTest{public

static

int

count=

0;public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);shellSort(data);print(data);}public

static

void

shellSort(int[]data){//計(jì)算出最大的h值int

h=

1;while

(h<=data.length/

3){h=h*

3

+

1;}while

(h>

0){for

(int

i=h;i<data.length;i+=h){if

(data[i]<data[i-h]){int

tmp=data[i];int

j=i-h;while

(j>=

0

&&data[j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//計(jì)算出下一個(gè)h值h=(h-

1)/

3;}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}

運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

71

3

6

2

5

9

4

8

71

2

3

6

5

9

4

8

71

2

3

5

6

9

4

8

71

2

3

4

5

6

9

8

71

2

3

4

5

6

8

9

71

2

3

4

5

6

7

8

91

2

3

4

5

6

7

8

9

上面程序在和直接插入法比較，會(huì)發(fā)現(xiàn)其與直接插入排序的差別在于：直接插入排序中的h會(huì)以1代替Shell排序是不穩(wěn)定的，它的空間開銷也是O(1),時(shí)間開銷估計(jì)在O(N3/2)~O(N7/6)之間Java排序算法（九）：歸并排序歸并排序（Merge）是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。歸并排序算法穩(wěn)定，數(shù)組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時(shí)間復(fù)雜度為O(nlog(n))，算法不是自適應(yīng)的，不需要對(duì)數(shù)據(jù)的隨機(jī)讀取。工作原理：1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置3、比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置4、重復(fù)步驟3直到某一指針達(dá)到序列尾5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾代碼實(shí)現(xiàn)：\o"viewplain"viewplainpublic

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("排序后的數(shù)組：");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;//對(duì)左邊數(shù)組進(jìn)行遞歸sort(data,left,center);//對(duì)右邊數(shù)組進(jìn)行遞歸sort(data,center+

1,right);//合并merge(data,left,center,right);print(data);}/***將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面2個(gè)數(shù)組已有序，歸并后依然有序**@paramdata*數(shù)組對(duì)象*@paramleft*左數(shù)組的第一個(gè)元素的索引*@paramcenter*左數(shù)組的最后一個(gè)元素的索引，center+1是右數(shù)組第一個(gè)元素的索引*@paramright*右數(shù)組最后一個(gè)元素的索引*/public

static

void

merge(int[]data,

int

left,

int

center,

int

right){//臨時(shí)數(shù)組int[]tmpArr=

new

int[data.length];//右數(shù)組第一個(gè)元素索引int

mid=center+

1;//third記錄臨時(shí)數(shù)組的索引int

third=left;//緩存左數(shù)組第一個(gè)元素的索引int

tmp=left;while

(left<=center&&mid<=right){//從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組if

(data[left]<=data[mid]){tmpArr[third++]=data[left++];}

else

{tmpArr[third++]=data[mid++];}}//剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while只會(huì)執(zhí)行其中一個(gè)）while

(mid<=right){tmpArr[third++]=data[mid++];}while

(left<=center){tmpArr[third++]=data[left++];}//將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中//（原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）while

(tmp<=right){data[tmp]=tmpArr[tmp++];}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

73

5

6

2

1

9

4

8

73

5

6

2

1

9

4

8

73

5

6

1

2

9

4

8

71

2

3

5

6

9

4

8

71

2

3

5

6

4

9

8

71

2

3

5

6

4

9

7

81

2

3

5

6

4

7

8

91

2

3

4

5

6

7

8

9排序后的數(shù)組：1

2

3

4

5

6

7

8

9Java排序算法（十）：桶式排序桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個(gè)特征：待排序列所有的值處于一個(gè)可枚舉的范圍之類；待排序列所在的這個(gè)可枚舉的范圍不應(yīng)該太大，否則排序開銷太大。排序的具體步驟如下：（1）對(duì)于這個(gè)可枚舉范圍構(gòu)建一個(gè)buckets數(shù)組，用于記錄“落入”每個(gè)桶中元素的個(gè)數(shù)；（2）將（1）中得到的buckets數(shù)組重新進(jìn)行計(jì)算，按如下公式重新計(jì)算：buckets[i]=buckets[i]+buckets[i-1](其中1<=i<buckets.length);桶式排序是一種非常優(yōu)秀的排序算法，時(shí)間效率極高，它只要通過2輪遍歷：第1輪遍歷待排數(shù)據(jù)，統(tǒng)計(jì)每個(gè)待排數(shù)據(jù)“落入”各桶中的個(gè)數(shù)，第2輪遍歷buckets用于重新計(jì)算buckets中元素的值，2輪遍歷后就可以得到每個(gè)待排數(shù)據(jù)在有序序列中的位置，然后將各個(gè)數(shù)據(jù)項(xiàng)依次放入指定位置即可。桶式排序的空間開銷較大，它需要兩個(gè)數(shù)組，第1個(gè)buckets數(shù)組用于記錄“落入”各桶中元素的個(gè)數(shù)，進(jìn)而保存各元素在有序序列中的位置，第2個(gè)數(shù)組用于緩存待排數(shù)據(jù)。桶式排序是穩(wěn)定的。如果待排序數(shù)據(jù)的范圍在0~k之間，那么它的時(shí)間復(fù)雜度是O(k+n)的桶式排序算法速度很快，因?yàn)樗臅r(shí)間復(fù)雜度是O(k+n)，而基于交換的排序時(shí)間上限是nlg

n。但是它的限制多，比如它只能排整形數(shù)組。而且當(dāng)k較大，而數(shù)組長(zhǎng)度n較小，即k>>n時(shí)，輔助數(shù)組C[k+1]的空間消耗較大。當(dāng)數(shù)組為整形，且k和n接近時(shí),可以用此方法排序。（有的文章也稱這種排序算法為“計(jì)數(shù)排序”）代碼實(shí)現(xiàn)：\o"viewplain"viewplainpublic

class

BucketSortTest{public

static

int

count=

0;public

static

void

main(String[]args){int[]data=

new

int[]{

5,

3,

6,

2,

1,

9,

4,

8,

7

};print(data);bucketSort(data,

0,

10);print(data);}public

static

void

bucketSort(int[]data,

int

min,

int

max){//緩存數(shù)組int[]tmp=

new

int[data.length];//buckets用于記錄待排序元素的信息//buckets數(shù)組定義了max-min個(gè)桶int[]buckets=

new

int[max-min];//計(jì)算每個(gè)元素在序列出現(xiàn)的次數(shù)for

(int

i=

0;i<data.length;i++){buckets[data[i]-min]++;}//計(jì)算“落入”各桶內(nèi)的元素在有序序列中的位置for

(int

i=

1;i<max-min;i++){buckets[i]=buckets[i]+buckets[i-

1];}//將data中的元素完全復(fù)制到tmp數(shù)組中System.arraycopy(data,

0,tmp,

0,data.length);//根據(jù)buckets數(shù)組中的信息將待排序列的各元素放入相應(yīng)位置for

(int

k=data.length-

1;k>=

0;k--){data[--buckets[tmp[k]-min]]=tmp[k];}}public

static

void

print(int[]data){for

(int

i=

0;i<data.length;i++){System.out.print(data[i]+

"\t");}System.out.println();}}

運(yùn)行結(jié)果：\o"viewplain"viewplain5

3

6

2

1

9

4

8

71

2

3

4

5

6

7

8

9Java排序算法（十一）：基數(shù)排序基數(shù)排序已經(jīng)不再是一種常規(guī)的排序方式，它更多地像一種排序方法的應(yīng)用，基數(shù)排序必須依賴于另外的排序方法。基數(shù)排序的總體思路就是將待排序數(shù)據(jù)拆分成多個(gè)關(guān)鍵字進(jìn)行排序，也就是說，基數(shù)排序的實(shí)質(zhì)是多關(guān)鍵字排序。多關(guān)鍵字排序的思路是將待排數(shù)據(jù)里德排序關(guān)鍵字拆分成多個(gè)排序關(guān)鍵字；第1個(gè)排序關(guān)鍵字，第2個(gè)排序關(guān)鍵字，第3個(gè)排序關(guān)鍵字......然后，根據(jù)子關(guān)鍵字對(duì)待排序數(shù)據(jù)進(jìn)行排序。多關(guān)鍵字排序時(shí)有兩種解決方案：最高位優(yōu)先法（MSD）(MostSignificantDigitfirst)最低位優(yōu)先法（LSD）(LeastSignificantDigitfirst)例如，對(duì)如下數(shù)據(jù)序列進(jìn)行排序。192,221,12,23可以觀察到它的每個(gè)數(shù)據(jù)至多只有3位，因此可以將每個(gè)數(shù)據(jù)拆分成3個(gè)關(guān)鍵字：百位（高位）、十位、個(gè)位（低位）。如果按照習(xí)慣思維，會(huì)先比較百位，百位大的數(shù)據(jù)大，百位相同的再比較十位，十位大的數(shù)據(jù)大；最后再比較個(gè)位。人得習(xí)慣思維是最高位優(yōu)先方式。如果按照人得思維方式，計(jì)算機(jī)實(shí)現(xiàn)起來有一定的困難，當(dāng)開始比較十位時(shí)，程序還需要判斷它們的百位是否相同--這就認(rèn)為地增加了難度，計(jì)算機(jī)通常會(huì)選擇最低位優(yōu)先法。基數(shù)排序方法對(duì)任一子關(guān)鍵字排序時(shí)必須借助于另一種排序方法，而且這種排序方法必