排序是程序開發(fā)中一種非常常見的操作，對一組任意的數(shù)據(jù)元素（或記錄）經(jīng)過排序操作后，就可以把他們變成一組按關(guān)鍵字排序的有序隊列。對一個排序算法來說，一般從下面3個方面來衡量算法的優(yōu)劣：時間復雜度：它主要是分析關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)?？臻g復雜度：分析排序算法中需要多少輔助內(nèi)存。穩(wěn)定性：若兩個記錄A和B的關(guān)鍵字值相等，但是排序后A,B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的；反之，就是不穩(wěn)定的。就現(xiàn)有的排序算法來看，排序大致可分為內(nèi)部排序和外部排序。如果整個排序過程不需要借助外部存儲器（如磁盤等），所有排序操作都是在內(nèi)存中完成，這種排序就被稱為內(nèi)部排序。如果參與排序的數(shù)據(jù)元素非常多，數(shù)據(jù)量非常大，計算無法把整個排序過程放在內(nèi)存中完成，必須借助于外部存儲器（如磁盤），這種排序就被稱為外部排序。外部排序最常用算噶是多路歸并排序，即將原文件分解稱多個能夠一次性裝入內(nèi)存的部分，分別把每一部分調(diào)入內(nèi)存完成排序，接下來再對多個有序的子文件進行歸并排序。就常用的內(nèi)部排序算法來說，可以分為以下幾類：選擇排序（直接選擇排序，堆排序）交換排序（冒泡排序，快速排序）插入排序（直接插入排序，折半插入排序，Shell排序）歸并排序桶式排序基數(shù)排序Java排序算法（二）：直接選擇排序直接選擇排序的基本操作就是每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完，它需要經(jīng)過n-1趟比較。算法不穩(wěn)定，O(1)的額外的空間，比較的時間復雜度為O(n^2)，交換的時間復雜度為O(n)，并不是自適應的。在大多數(shù)情況下都不推薦使用。只有在希望減少交換次數(shù)的情況下可以用?；舅枷雗個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。②第1趟排序在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)?！鄣趇趟排序第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。算法實現(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();}}運行結(jié)果：\o"viewplain"viewplain536219487136259487126359487123659487123459687123456987123456789123456789Java排序算法（三）：堆排序堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結(jié)構(gòu)所設(shè)計的一種排序算法，可以利用數(shù)組的特點快速定位指定索引的元素。堆排序是不穩(wěn)定的排序方法，輔助空間為O(1)，最壞時間復雜度為O(nlog2n)，堆排序的堆序的平均性能較接近于最壞性能。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。（1）用大根堆排序的基本思想①先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū)②再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key③由于交換后新的根R[1]可能違反堆性質(zhì)，故應將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄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)整為堆?！钡綗o序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作：①初始化操作：將R[1..n]構(gòu)造為初始堆；②每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。注意：①只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。代碼實現(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--){//保存當前正在判斷的節(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應該等于lastIndexif

(data[biggerIndex]<data[biggerIndex+

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

(data[k]<data[biggerIndex]){//若當前節(jié)點值比子節(jié)點最大值小，則交換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();}}

運行結(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

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

運行結(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排序算法（五）：快速排序快速排序是一個速度非常快的交換排序算法，它的基本思路很簡單，從待排的數(shù)據(jù)序列中任取一個數(shù)據(jù)（如第一個數(shù)據(jù)）作為分界值，所有比它小的數(shù)據(jù)元素放到左邊，所有比它大的數(shù)據(jù)元素放到它的右邊。經(jīng)過這樣一趟下來，該序列形成左右兩個子序列，左邊序列中的數(shù)據(jù)元素的值都比分界值小，右邊序列中數(shù)據(jù)元素的值都比分界值大。

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

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

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

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

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

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

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

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

平均時間復雜度為：：T(n)=O(nlogn)代碼實現(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;//以起始索引為分界點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和分界點的值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();}}

運行結(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ù)總和為（0+1+...+n-1）=O(n^2)。其他情況下也要考慮移動元素的次數(shù)，故時間復雜度為O(n^2)直接插入空間效率很好，只需要1個緩存數(shù)據(jù)單元，也就是說空間復雜度為O(1).直接插入排序是穩(wěn)定的。直接插入排序在數(shù)據(jù)已有一定順序的情況下，效率較好。但如果數(shù)據(jù)無規(guī)則，則需要移動大量的數(shù)據(jù)，其效率就與冒泡排序法和選擇排序法一樣差了。算法描述對一個有n個元素的數(shù)據(jù)序列，排序需要進行n-1趟插入操作：第1趟插入，將第2個元素插入前面的有序子序列--此時前面只有一個元素，當然是有序的。第2趟插入，將第3個元素插入前面的有序子序列，前面2個元素是有序的。第n-1趟插入，將第n個元素插入前面的有序子序列，前面n-1個元素是有序的。代碼實現(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();}}

運行結(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人閱讀

評論(2)

\o"收藏"收藏

\o"舉報"舉報Java排序算法（七）：折半插入排序折半插入排序法，又稱二分插入排序法，是直接插入排序法的改良版，也需要執(zhí)行i-1趟插入，不同之處在于，第i趟插入，先找出第i+1個元素應該插入的的位置，假定前i個數(shù)據(jù)是已經(jīng)處于有序狀態(tài)。代碼實現(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ù)整體向后移動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();}}運行結(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行了簡單的改進：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進行插入排序，從而使數(shù)據(jù)項大跨度地移動，當這些數(shù)據(jù)項排過一趟序之后，希爾排序算法減小數(shù)據(jù)項的間隔再進行排序，依次進行下去，進行這些排序時的數(shù)據(jù)項之間的間隔被稱為增量，習慣上用字母h來表示這個增量。常用的h序列由Knuth提出，該序列從1開始，通過如下公式產(chǎn)生：h=3*h+1反過來程序需要反向計算h序列，應該使用h=(h-1)/3代碼實現(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){//計算出最大的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);}}//計算出下一個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();}}

運行結(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

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

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

static

void

merge(int[]data,

int

left,

int

center,

int

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

new

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

mid=center+

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

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

tmp=left;while

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

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

else

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

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

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

n。但是它的限制多，比如它只能排整形數(shù)組。而且當k較大，而數(shù)組長度n較小，即k>>n時，輔助數(shù)組C[k+1]的空間消耗較大。當數(shù)組為整形，且k和n接近時,可以用此方法排序。（有的文章也稱這種排序算法為“計數(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個桶int[]buckets=

new

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

(int

i=

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

(int

i=

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

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

0,tmp,

0,data.length);//根據(jù)buckets數(shù)組中的信息將待排序列的各元素放入相應位置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();}}

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