張帥 方歡 丁飛

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

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

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

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

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

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

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

1.1冒泡排序

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

1.2選擇排序

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

1.3插入排序

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

1.4希爾排序

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

1.5歸并排序

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

1.6快速排序

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

1.7堆排序

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

1.8計數(shù)排序

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

1.9桶排序

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

1.10基數(shù)排序

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

2實際效率測試

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

2.1設(shè)計測試程序

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

2.2測試結(jié)果

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

2.3結(jié)論

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

參考文獻(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é)報（自然科學(xué)版），2001，11（1）：9-12.

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

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