這篇文章主要為大家展示了“Java如何實(shí)現(xiàn)排序算法”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java如何實(shí)現(xiàn)排序算法”這篇文章吧。

創(chuàng)新互聯(lián)建站從2013年成立，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元敖漢做網(wǎng)站,已為上家服務(wù),為敖漢各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話(huà):028-86922220

Java實(shí)現(xiàn)的5大排序算法
排序算法很多地方都會(huì)用到，近期又重新看了一遍算法，并自己簡(jiǎn)單地實(shí)現(xiàn)了一遍，特此記錄下來(lái)，為以后復(fù)習(xí)留點(diǎn)材料。

下面逐一看看經(jīng)典的排序算法：

1、Java排序算法之選擇排序

選擇排序的基本思想是遍歷數(shù)組的過(guò)程中，以 i 代表當(dāng)前需要排序的序號(hào)，則需要在剩余的 [i…n-1] 中找出其中的最小值，然后將找到的最小值與 i 指向的值進(jìn)行交換。因?yàn)槊恳惶舜_定元素的過(guò)程中都會(huì)有一個(gè)選擇最大值的子流程，所以人們形象地稱(chēng)之為選擇排序。

舉個(gè)實(shí)例來(lái)看看：

1.初始： [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]

2.3.i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])

4.5.i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])

6.7.i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])

8.9.i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 無(wú)需交換 )

10.11.i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])

12.13.i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])

14.15.i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])

16.17.i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無(wú)需交換 )

18.19.i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無(wú)需交換 )

20.21.i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無(wú)需交換 )

由例子可以看出，選擇排序隨著排序的進(jìn)行( i 逐漸增大)，比較的次數(shù)會(huì)越來(lái)越少，但是不論數(shù)組初始是否有序，選擇排序都會(huì)從 i 至數(shù)組末尾進(jìn)行一次選擇比較，所以給定長(zhǎng)度的數(shù)組，選擇排序的比較次數(shù)是固定的： 1 + 2 + 3 + … + n = n * (n + 1) / 2 ,而交換的次數(shù)則跟初始數(shù)組的順序有關(guān)，如果初始數(shù)組順序?yàn)殡S機(jī)，則在最壞情況下，數(shù)組元素將會(huì)交換 n 次，最好的情況下則可能 0 次(數(shù)組本身即為有序)。

由此可以推出，選擇排序的時(shí)間復(fù)雜度和空間復(fù)雜度分別為 O(n2 )和 O(1)(選擇排序只需要一個(gè)額外空間用于數(shù)組元素交換)。

實(shí)現(xiàn)代碼：

1./**

2. * Selection Sorting

3. */

4.SELECTION(new Sortable() {

5. public

6. int len = array.length;

7. for (int i = 0; i < len; i++) {

8. int selected = i;

9. for (int j = i + 1; j < len; j++) {

10. int compare = array[j].compareTo(array[selected]);

11. if (compare != 0 && compare < 0 == ascend) {

12. selected = j;

13. }

14. }

15.16. exchange(array, i, selected);

17. }

18. }

19.})

2、Java排序算法之插入排序

插入排序的基本思想是在遍歷數(shù)組的過(guò)程中，假設(shè)在序號(hào) i 之前的元素即 [0i-1] 都已經(jīng)排好序，本趟需要找到 i 對(duì)應(yīng)的元素 x 的正確位置 k ,并且在尋找這個(gè)位置 k 的過(guò)程中逐個(gè)將比較過(guò)的元素往后移一位，為元素 x "騰位置",最后將 k 對(duì)應(yīng)的元素值賦為 x ,插入排序也是根據(jù)排序的特性來(lái)命名的。

以下是一個(gè)實(shí)例，紅色 標(biāo)記的數(shù)字為插入的數(shù)字，被劃掉的數(shù)字是未參與此次排序的元素，紅色 標(biāo)記的數(shù)字與被劃掉數(shù)字之間的元素為逐個(gè)向后移動(dòng)的元素，比如第二趟參與排序的元素為 [11, 31, 12] ,需要插入的元素為 12 ,但是 12 當(dāng)前并沒(méi)有處于正確的位置，于是我們需要依次與前面的元素 31 、 11 做比較，一邊比較一邊移動(dòng)比較過(guò)的元素，直到找到第一個(gè)比 12 小的元素 11 時(shí)停止比較，此時(shí) 31 對(duì)應(yīng)的索引 1 則是 12 需要插入的位置。

1.初始： [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]

2.3.第一趟： [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (無(wú)移動(dòng)的元素)

4.5.第二趟： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] ( 31 向后移動(dòng))

6.7.第三趟： [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] ( 11, 12, 31 皆向后移動(dòng))

8.9.第四趟： [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (無(wú)移動(dòng)的元素)

10.11.第五趟： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] ( 31, 34 向后移動(dòng))

12.13.第六趟： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] ( 30, 31, 34 向后移動(dòng))

14.15.第七趟： [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (無(wú)移動(dòng)的元素)

16.17.第八趟： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] ( 38 向后移動(dòng))

18.19.第九趟： [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] ( 26, 30, 31, 34, 36, 38 向后移動(dòng))

插入排序會(huì)優(yōu)于選擇排序，理由是它在排序過(guò)程中能夠利用前部分?jǐn)?shù)組元素已經(jīng)排好序的一個(gè)優(yōu)勢(shì)，有效地減少一些比較的次數(shù)，當(dāng)然這種優(yōu)勢(shì)得看數(shù)組的初始順序如何，最壞的情況下(給定的數(shù)組恰好為倒序)插入排序需要比較和移動(dòng)的次數(shù)將會(huì)等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,這種極端情況下，插入排序的效率甚至比選擇排序更差。因此插入排序是一個(gè)不穩(wěn)定的排序方法，插入效率與數(shù)組初始順序息息相關(guān)。一般情況下，插入排序的時(shí)間復(fù)雜度和空間復(fù)雜度分別為 O(n2 ) 和 O(1) .

實(shí)現(xiàn)代碼：

1./**

2. * Insertion Sorting

3. */

4.INSERTION(new Sortable() {

5. public

6. int len = array.length;

7. for (int i = 1; i < len; i++) {

8. T toInsert = array[i];

9. int j = i;

10. for (; j > 0; j--) {

11. int compare = array[j - 1].compareTo(toInsert);

12. if (compare == 0 || compare < 0 == ascend) {

13. break;

14. }

15. array[j] = array[j - 1];

16. }

17.

18. array[j] = toInsert;

19. }

20. }

21.})

3、Java排序算法之冒泡排序

冒泡排序可以算是最經(jīng)典的排序算法了，記得小弟上學(xué)時(shí)最先接觸的也就是這個(gè)算法了，因?yàn)閷?shí)現(xiàn)方法最簡(jiǎn)單，兩層 for 循環(huán)，里層循環(huán)中判斷相鄰兩個(gè)元素是否逆序，是的話(huà)將兩個(gè)元素交換，外層循環(huán)一次，就能將數(shù)組中剩下的元素中最小的元素"浮"到最前面，所以稱(chēng)之為冒泡排序。

照例舉個(gè)簡(jiǎn)單的實(shí)例吧：

1.

2.

3.初始狀態(tài)： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]

4.

5.內(nèi)層第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] ( 9th [23]<->8th [38 )

6.

7.內(nèi)層第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] ( 8th [23]<->7th [29] )

8.

9.內(nèi)層第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] ( 7th [23]<->6th [31] )

10.

11.內(nèi)層第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] ( 7 、 23 都位于正確的順序，無(wú)需交換)

12.

13.內(nèi)層第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] ( 5th [7]<->4th [36] )

14.

15.內(nèi)層第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] ( 4th [7]<->3rd [39] )

16.

17.內(nèi)層第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] ( 3rd [7]<->2nd [26] )

18.

19.內(nèi)層第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] ( 2nd [7]<->1st [19] )

20.

21.內(nèi)層第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] ( 1st [7]<->0th [24] )

22.

23.……

其實(shí)冒泡排序跟選擇排序比較相像，比較次數(shù)一樣，都為 n * (n + 1) / 2 ,但是冒泡排序在挑選最小值的過(guò)程中會(huì)進(jìn)行額外的交換(冒泡排序在排序中只要發(fā)現(xiàn)相鄰元素的順序不對(duì)就會(huì)進(jìn)行交換，與之對(duì)應(yīng)的是選擇排序，只會(huì)在內(nèi)層循環(huán)比較結(jié)束之后根據(jù)情況決定是否進(jìn)行交換)，所以在我看來(lái)，選擇排序?qū)儆诿芭菖判虻母倪M(jìn)版。

實(shí)現(xiàn)代碼：

1./**

2. * Bubble Sorting, it's very similar with Insertion Sorting

3. */

4.BUBBLE(new Sortable() {

5. public

6. int length = array.length;

7. int lastExchangedIdx = 0;

8. for (int i = 0; i < length; i++) {

9. // mark the flag to identity whether exchange happened to false

10. boolean isExchanged = false;

11. // last compare and exchange happened before reaching index i

12. int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;

13. for (int j = length - 1; j > currOrderedIdx; j--) {

14. int compare = array[j - 1].compareTo(array[j]);

15. if (compare != 0 && compare > 0 == ascend) {

16. exchange(array, j - 1, j);

17. isExchanged = true;

18. lastExchangedIdx = j;

19. }

20. }

21. // if no exchange happen means array is already in order

22. if (isExchanged == false) {

23. break;

24. }

25. }

26. }

27.})

4、Java排序算法之希爾排序

希爾排序的誕生是由于插入排序在處理大規(guī)模數(shù)組的時(shí)候會(huì)遇到需要移動(dòng)太多元素的問(wèn)題。希爾排序的思想是將一個(gè)大的數(shù)組"分而治之",劃分為若干個(gè)小的數(shù)組，以 gap 來(lái)劃分，比如數(shù)組 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 來(lái)劃分，可以分為 [1, 3, 5, 7] 和 [2, 4, 6, 8] 兩個(gè)數(shù)組(對(duì)應(yīng)的，如 gap = 3 ,則劃分的數(shù)組為： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分別對(duì)劃分出來(lái)的數(shù)組進(jìn)行插入排序，待各個(gè)子數(shù)組排序完畢之后再減小 gap 值重復(fù)進(jìn)行之前的步驟，直至 gap = 1 ,即對(duì)整個(gè)數(shù)組進(jìn)行插入排序，此時(shí)的數(shù)組已經(jīng)基本上快排好序了，所以需要移動(dòng)的元素會(huì)很小很小，解決了插入排序在處理大規(guī)模數(shù)組時(shí)較多移動(dòng)次數(shù)的問(wèn)題。

具體實(shí)例請(qǐng)參照插入排序。

希爾排序是插入排序的改進(jìn)版，在數(shù)據(jù)量大的時(shí)候?qū)π实奶嵘龓椭艽螅瑪?shù)據(jù)量小的時(shí)候建議直接使用插入排序就好了。 實(shí)現(xiàn)代碼：

1./**

2. * Shell Sorting

3. */

4.SHELL(new Sortable() {

5. public

6. int length = array.length;

7. int gap = 1;

8.

9. // use the most next to length / 3 as the first gap

10. while (gap < length / 3) {

11. gap = gap * 3 + 1;

12. }

13.

14. while (gap >= 1) {

15. for (int i = gap; i < length; i++) {

16. T next = array[i];

17. int j = i;

18. while (j >= gap) {

19. int compare = array[j - gap].compareTo(next);

20. // already find its position

21. if (compare == 0 || compare < 0 == ascend) {

22. break;

23. }

24.

25. array[j] = array[j - gap];

26. j -= gap;

27. }

28. if (j != i) {

29. array[j] = next;

30. }

31. }

32. gap /= 3;

33. }

34.

35. }

36.})

5、Java排序算法之歸并排序

歸并排序采用的是遞歸來(lái)實(shí)現(xiàn)，屬于"分而治之",將目標(biāo)數(shù)組從中間一分為二，之后分別對(duì)這兩個(gè)數(shù)組進(jìn)行排序，排序完畢之后再將排好序的兩個(gè)數(shù)組"歸并"到一起，歸并排序最重要的也就是這個(gè)"歸并"的過(guò)程，歸并的過(guò)程中需要額外的跟需要?dú)w并的兩個(gè)數(shù)組長(zhǎng)度一致的空間，比如需要規(guī)定的數(shù)組分別為： [3, 6, 8, 11] 和 [1, 3, 12, 15] (雖然邏輯上被劃為為兩個(gè)數(shù)組，但實(shí)際上這些元素還是位于原來(lái)數(shù)組中的，只是通過(guò)一些 index 將其劃分成兩個(gè)數(shù)組，原數(shù)組為 [3, 6, 8, 11, 1, 3, 12, 15 ,我們?cè)O(shè)置三個(gè)指針 lo, mid, high 分別為 0,3,7 就可以實(shí)現(xiàn)邏輯上的子數(shù)組劃分)那么需要的額外數(shù)組的長(zhǎng)度為 4 + 4 = 8 .歸并的過(guò)程可以簡(jiǎn)要地概括為如下：

1)將兩個(gè)子數(shù)組中的元素復(fù)制到新數(shù)組 copiedArray 中，以前面提到的例子為例，則 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ;

2)設(shè)置兩個(gè)指針?lè)謩e指向原子數(shù)組中對(duì)應(yīng)的第一個(gè)元素，假定這兩個(gè)指針取名為 leftIdx 和 rightIdx ,則 leftIdx = 0 (對(duì)應(yīng) copiedArray 中的第一個(gè)元素 [3] )， rightIdx = 4 (對(duì)應(yīng) copiedArray 中的第五個(gè)元素 [1] );

3)比較 leftIdx 和 rightIdx 指向的數(shù)組元素值，選取其中較小的一個(gè)并將其值賦給原數(shù)組中對(duì)應(yīng)的位置 i ,賦值完畢后分別對(duì)參與賦值的這兩個(gè)索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已經(jīng)達(dá)到對(duì)應(yīng)數(shù)組的末尾，則余下只需要將剩下數(shù)組的元素按順序 copy 到余下的位置即可。

下面給個(gè)歸并的具體實(shí)例：

1.第一趟：

2.3.輔助數(shù)組 [21 , 28, 39 | 35, 38] (數(shù)組被拆分為左右兩個(gè)子數(shù)組，以 | 分隔開(kāi))

4.5.[21 , , , , ] (第一次 21 與 35 比較 , 左邊子數(shù)組勝出， leftIdx = 0 , i = 0 )

6.7.第二趟：

8.9.輔助數(shù)組 [21, 28 , 39 | 35, 38]

10.11.[21 , 28, , , ] (第二次 28 與 35 比較，左邊子數(shù)組勝出， leftIdx = 1 , i = 1 )

12.13.第三趟： [21, 28, 39 | 35 , 38]

14.15.[21 , 28 , 35, , ] (第三次 39 與 35 比較，右邊子數(shù)組勝出， rightIdx = 0 , i = 2 )

16.17.第四趟： [21, 28, 39 | 35, 38 ]

18.19.[21 , 28 , 35 , 38, ] (第四次 39 與 38 比較，右邊子數(shù)組勝出， rightIdx = 1 , i = 3 )

20.21.第五趟： [21, 28, 39 | 35, 38]

22.23.[21 , 28 , 35 , 38 , 39] (第五次時(shí)右邊子數(shù)組已復(fù)制完，無(wú)需比較 leftIdx = 2 , i = 4 )

以上便是一次歸并的過(guò)程，我們可以將整個(gè)需要排序的數(shù)組做有限次拆分(每次一分為二)直到分為長(zhǎng)度為 1 的小數(shù)組為止，長(zhǎng)度為 1 時(shí)數(shù)組已經(jīng)不用排序了。在這之后再逆序(由于采用遞歸)依次對(duì)這些數(shù)組進(jìn)行歸并操作，直到最后一次歸并長(zhǎng)度為 n / 2 的子數(shù)組，歸并完成之后數(shù)組排序也完成。

歸并排序需要的額外空間是所有排序中最多的，每次歸并需要與參與歸并的兩個(gè)數(shù)組長(zhǎng)度之和相同個(gè)元素(為了提供輔助數(shù)組)。則可以推斷歸并排序的空間復(fù)雜度為 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判斷)，時(shí)間復(fù)雜度比較難估，這里小弟也忘記是多少了(囧)。

實(shí)現(xiàn)代碼：

1./**

2. * Merge sorting

3. */

4.MERGE(new Sortable() {

5. public

6. this.sort(array, 0, array.length - 1, ascend);

7. }

8.9. private

10. // OPTIMIZE ONE

11. // if the substring's length is less than 20,

12. // use insertion sort to reduce recursive invocation

13. if (hi - lo < 20) {

14. for (int i = lo + 1; i <= hi; i++) {

15. T toInsert = array[i];

16. int j = i;

17. for (; j > lo; j--) {

18. int compare = array[j - 1].compareTo(toInsert);

19. if (compare == 0 || compare < 0 == ascend) {

20. break;

21. }

22. array[j] = array[j - 1];

23. }

24.25. array[j] = toInsert;

26. }

27.28. return;

29. }

30.31. int mid = lo + (hi - lo) / 2;

32. sort(array, lo, mid, ascend);

33. sort(array, mid + 1, hi, ascend);

34. merge(array, lo, mid, hi, ascend);

35. }

36.37. private

38. // OPTIMIZE TWO

39. // if it is already in right order, skip this merge

40. // since there's no need to do so

41. int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);

42. if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {

43. return;

44. }

45.46. @SuppressWarnings("unchecked")

47. T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];

48. System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);

49.50. int lowIdx = 0;

51. int highIdx = mid - lo + 1;

52.53. for (int i = lo; i <= hi; i++) {

54. if (lowIdx > mid - lo) {

55. // left sub array exhausted

56. array[i] = arrayCopy[highIdx++];

57. } else if (highIdx > hi - lo) {

58. // right sub array exhausted

59. array[i] = arrayCopy[lowIdx++];

60. } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {

61. array[i] = arrayCopy[lowIdx++];

62. } else {

63. array[i] = arrayCopy[highIdx++];

64. }

65. }

66. }

67.})

以上是“Java如何實(shí)現(xiàn)排序算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

新聞標(biāo)題：Java如何實(shí)現(xiàn)排序算法
文章地址：http://aaarwkj.com/article0/igcpoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站維護(hù)、Google、虛擬主機(jī)、品牌網(wǎng)站建設(shè)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)