基于Java語言對(duì)10種經(jīng)典排序算法的研究

張帥 方歡 丁飛

摘要：排序算法是算法中最為基礎(chǔ)的算法，其在很多的領(lǐng)域中都得到了相當(dāng)?shù)闹匾?，在?duì)于大量數(shù)據(jù)的處理方面，排序算法有著極其重要的作用。排序算法的種類有很多，為找出一種效率較高的排序算法，基于Java語言對(duì)10種經(jīng)典排序算法進(jìn)行實(shí)現(xiàn)和測試，通過對(duì)結(jié)果的分析，判斷每種排序算法的運(yùn)行時(shí)間及效率，對(duì)10種經(jīng)典排序算法的運(yùn)行效率進(jìn)行排序。

關(guān)鍵詞：排序算法;Java語言;運(yùn)行效率;運(yùn)行時(shí)間;數(shù)據(jù)處理

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)：1009-3044（2020）25-0223-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

排序算法作為算法中的基礎(chǔ)算法在各領(lǐng)域中都有著至關(guān)重要的作用，一種排序算法的效率程度往往影響著數(shù)據(jù)分析的效率和時(shí)間，因此一個(gè)優(yōu)秀的排序算法，不僅僅是實(shí)現(xiàn)對(duì)數(shù)據(jù)的排序功能，還要能夠在較短的時(shí)間內(nèi)，對(duì)大量的數(shù)據(jù)進(jìn)行排序[1]。本文基于Java語言對(duì)10種經(jīng)典排序算法，并編寫相關(guān)程序?qū)ζ鋾r(shí)間效率進(jìn)行分析。

1十種經(jīng)典排序算法

1.1冒泡排序

冒泡排序作為排序算法中最為基礎(chǔ)，最為簡單的算法，它重復(fù)的遍歷需要排序的數(shù)組，每一次比較相鄰的兩個(gè)元素，并根據(jù)順序進(jìn)行交換，直到無須交換為止。實(shí)現(xiàn)代碼如1-1。

1.2選擇排序

選擇排序則是遍歷一次數(shù)組，從中找出最大（?。┰兀诺綌?shù)組的末尾（開頭），將剩余的元素再次遍歷，繼續(xù)尋找最大（?。┰兀浪性嘏判蚓判蛲戤?。實(shí)現(xiàn)代碼如1-2。

1.3插入排序

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

1.4希爾排序

希爾排序是插入排序的一種改進(jìn)版本，希爾排序是將整個(gè)待排序的組數(shù)分割成為若干個(gè)子序列，并在子序列中使用插入排序，并不斷擴(kuò)大子序列的長度，最終實(shí)現(xiàn)全體有序[3]。

1.5歸并排序

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

1.6快速排序

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

1.7堆排序

堆排序利用了堆的數(shù)據(jù)結(jié)構(gòu)，其性質(zhì)為子節(jié)點(diǎn)的值總是小于或大于其父節(jié)點(diǎn)，堆排序正式利用了此性質(zhì)來進(jìn)行排序。

1.8計(jì)數(shù)排序

計(jì)數(shù)排序是一特殊的排序算法，其核心為開辟一個(gè)額外的數(shù)組，統(tǒng)計(jì)待排序數(shù)組中每個(gè)元素值i出現(xiàn)的次數(shù)，計(jì)入額外數(shù)組的第i項(xiàng)，再根據(jù)額外數(shù)組沒項(xiàng)的值反向輸出，便可完成排序，計(jì)數(shù)排序常常用來解決對(duì)數(shù)字的排序。

1.9桶排序

桶排序相當(dāng)于計(jì)數(shù)排序的升級(jí)版。它增強(qiáng)了函數(shù)的映射關(guān)系，使得算法能夠更加的高效，它將每一個(gè)元素都通過映射函數(shù)映射到桶中，再將其排序，最后將每個(gè)桶按序輸出。

1.10基數(shù)排序

基數(shù)排序也是桶排序的一種變型，其原理是將每個(gè)數(shù)字按照位數(shù)切割，并按照每個(gè)位數(shù)進(jìn)行排序操作。其相當(dāng)于按照位數(shù)來分配桶[5]。

2實(shí)際效率測試

對(duì)于此10種經(jīng)典排序算法，我們將基于java語言設(shè)計(jì)程序來測試每種排序算法針對(duì)不同規(guī)模的數(shù)據(jù)的運(yùn)行時(shí)間，并對(duì)其運(yùn)行時(shí)間數(shù)據(jù)進(jìn)行統(tǒng)計(jì)和分析。

2.1設(shè)計(jì)測試程序

利用java語言設(shè)計(jì)測試程序，使得每種排序算法能夠在不同的數(shù)據(jù)規(guī)模統(tǒng)計(jì)其排序所使用的時(shí)間。程序代碼展示如下：

2.2測試結(jié)果

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

2.3結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

【通聯(lián)編輯：梁書】