基于Java語言對10種經典排序算法的研究

張帥 方歡 丁飛

摘要：排序算法是算法中最為基礎的算法，其在很多的領域中都得到了相當的重視，在對于大量數據的處理方面，排序算法有著極其重要的作用。排序算法的種類有很多，為找出一種效率較高的排序算法，基于Java語言對10種經典排序算法進行實現和測試，通過對結果的分析，判斷每種排序算法的運行時間及效率，對10種經典排序算法的運行效率進行排序。

關鍵詞：排序算法;Java語言;運行效率;運行時間;數據處理

中圖分類號：TP311文獻標識碼： A

文章編號：1009-3044（2020）25-0223-03

開放科學（資源服務）標識碼（OSID）：

排序算法作為算法中的基礎算法在各領域中都有著至關重要的作用，一種排序算法的效率程度往往影響著數據分析的效率和時間，因此一個優秀的排序算法，不僅僅是實現對數據的排序功能，還要能夠在較短的時間內，對大量的數據進行排序[1]。本文基于Java語言對10種經典排序算法，并編寫相關程序對其時間效率進行分析。

1十種經典排序算法

1.1冒泡排序

冒泡排序作為排序算法中最為基礎，最為簡單的算法，它重復的遍歷需要排序的數組，每一次比較相鄰的兩個元素，并根據順序進行交換，直到無須交換為止。實現代碼如1-1。

1.2選擇排序

選擇排序則是遍歷一次數組，從中找出最大（小）元素，放到數組的末尾（開頭），將剩余的元素再次遍歷，繼續尋找最大（小）元素，知道所有元素排序均排序完畢。實現代碼如1-2。

1.3插入排序

插入排序是一種重要的排序算法，其原理是最容易理解的排序算法，可以將其形象地比喻為摸撲克牌，每次加入一個元素，將加入的元素插入到有序序列的適當位置，并再加入一個新元素，重復操作，直到所有元素均有序。

1.4希爾排序

希爾排序是插入排序的一種改進版本，希爾排序是將整個待排序的組數分割成為若干個子序列，并在子序列中使用插入排序，并不斷擴大子序列的長度，最終實現全體有序[3]。

1.5歸并排序

歸并排序體現出了分治法的思想[4]，其思想為先劃分，在合并，將待排序列每次分為兩個大小相等的子序列，并將子序列排序，使用兩個指針，將兩個序列中較小的元素放入到合并空間中，并移動指針到下一個元素，直到合并完畢。

1.6快速排序

與歸并排序相類似，歸并排序注重合并，而快速排序則注重劃分，從數組中挑選一個元素作為基準，在劃分時，將比基準小的元素放到左邊，將比基準大的元素放到右邊，然后遞歸地把兩個子序列排序，直到所有元素全部排序完畢。

1.7堆排序

堆排序利用了堆的數據結構，其性質為子節點的值總是小于或大于其父節點，堆排序正式利用了此性質來進行排序。

1.8計數排序

計數排序是一特殊的排序算法，其核心為開辟一個額外的數組，統計待排序數組中每個元素值i出現的次數，計入額外數組的第i項，再根據額外數組沒項的值反向輸出，便可完成排序，計數排序常常用來解決對數字的排序。

1.9桶排序

桶排序相當于計數排序的升級版。它增強了函數的映射關系，使得算法能夠更加的高效，它將每一個元素都通過映射函數映射到桶中，再將其排序，最后將每個桶按序輸出。

1.10基數排序

基數排序也是桶排序的一種變型，其原理是將每個數字按照位數切割，并按照每個位數進行排序操作。其相當于按照位數來分配桶[5]。

2實際效率測試

對于此10種經典排序算法，我們將基于java語言設計程序來測試每種排序算法針對不同規模的數據的運行時間，并對其運行時間數據進行統計和分析。

2.1設計測試程序

利用java語言設計測試程序，使得每種排序算法能夠在不同的數據規模統計其排序所使用的時間。程序代碼展示如下：

2.2測試結果

由于基數排序受到數據位數的限制，導致基數排序的數組需要重新獲得，中間隨機數較多，并且數據位數越大所需時間越多，因此基數排序只選擇到500000條。

2.3結論

從表格中可以看出，在數據量較小時，10種排序算法的時間相差不大，但隨著數據量的不斷增加，冒泡排序，選擇排序，插入排序，希爾排序的時間增長迅速，且當數據大于10000000時，處理此規模所需要的時間會更長，因此無法做出有效的統計。而歸并排序、快速排序、堆排序可以處理大規模的數據，但所需時間也較長。而計數排序、桶排序可以有效地解決大規模數據的問題，但是其缺點為需要開辟大量的額外空間來對數據進行統計。

參考文獻：

[1]RebertSedgewick，KevinWanyne.算法[M].謝路云，譯.北京：人民郵電出版社，2012.

[2] 吳光生，范德斌.排序算法研究[J].軟件導刊，2007（4）：97-98.

[3] 劉齊銳.基本排序算法研究[J].通訊世界，2018（5）：295-296.

[4] 肖建華，尋大勇，趙艷紅.排序算法中的分治策略[J].湖南工程學院學報（自然科學版），2001，11（1）：9-12.

[5]https：//www.runoob.com/w3cnote/ten-sorting-algorithm.html.2018.

【通聯編輯：梁書】