經(jīng)典的排序算法有八種，分別為：

• 冒泡排序
• 選擇排序
• 插入排序
• 歸并排序
• 希爾排序
• 快速排序
• 堆排序
• 基數(shù)排序

其中冒泡排序、選擇排序、插入排序稱為三大基本排序。

雖然這三大基本排序算法時(shí)間復(fù)雜度都是O(n2)，但是其實(shí)細(xì)細(xì)討論之下，還是有各自的特點(diǎn)的。

1.冒泡排序

冒泡排序法的思路

基本思路：

假設(shè)我們需要進(jìn)行升序排列

進(jìn)行N輪的比較，每一輪將相鄰的兩個(gè)元素依次比較，根據(jù)大小進(jìn)行交換，每輪比較結(jié)束后，將最大的元素依次‘冒’到數(shù)組的末尾，經(jīng)過幾輪比較后，數(shù)組就會(huì)呈現(xiàn)有序的狀態(tài)。

圖解：

2)后面每輪都按照此方法進(jìn)行比較，但是需要注意，此后的每一輪都需要比前一輪少比較一次，因?yàn)榍懊嬉呀?jīng)確定了最大元素的位置，為了提高性能，可以不用再和后面確定了位置的元素進(jìn)行比較。

3)由此可以確定，當(dāng)數(shù)組的長(zhǎng)度為N時(shí)，需要比較的輪數(shù)為N-1輪。每輪中從第一個(gè)元素開始相鄰元素兩兩進(jìn)行比較，第一輪需要比較N-1次，第2輪需要比較N-2次，依次類推，實(shí)現(xiàn)整體排序。

2.冒泡排序法的代碼實(shí)現(xiàn)

• 首先通過一個(gè)外層的for循環(huán)確定比較的輪數(shù)，循環(huán)元素?cái)?shù)量-1輪。
• 內(nèi)部通過一個(gè)for循環(huán)實(shí)現(xiàn)每輪的兩兩元素比較的效果。每輪需要比較的次數(shù)都會(huì)比上一輪減少一次，通過j
• 元素兩兩比較通過array[j] > array[j+1]來實(shí)現(xiàn)。

3.冒泡排序法優(yōu)化

以上的冒泡排序法還有優(yōu)化的空間。因?yàn)槿绻粋€(gè)數(shù)組已經(jīng)是完全有序的情況下，冒泡排序法仍然會(huì)進(jìn)行逐輪的比較，這無疑是浪費(fèi)性能的行為。因此我們可以確定，當(dāng)冒泡的比較中，有一輪如果沒有發(fā)生交換，則可以確定當(dāng)前數(shù)組已經(jīng)完全有序，后面的輪數(shù)完全不必在進(jìn)行。故做以下的調(diào)整：

通過定義一個(gè)標(biāo)識(shí)符isSort，如果有一輪沒有發(fā)生任何交換，則isSort就會(huì)為true，下次直接break，后面的輪數(shù)就不用再進(jìn)行比較了。

4.選擇排序

選擇排序的思路

基本思路：

選擇排序和冒泡排序不同，選擇排序會(huì)通過一輪比較，選出最小的那個(gè)元素的下標(biāo)，然后和第一個(gè)元素進(jìn)行交換，這樣第一個(gè)元素的位置就可以確定了。

第二輪如法炮制，從第二個(gè)元素開始依次比較，選出最小的元素的下標(biāo)，和第二個(gè)元素交換位置，這樣第二小的元素位置就確定了。

后面依次類推，直到整個(gè)數(shù)組呈現(xiàn)有序狀態(tài)。

選擇排序法的代碼實(shí)現(xiàn)：

• 選擇排序比較的輪數(shù)和冒泡排序比較的輪數(shù)是一樣的
• K表示當(dāng)前最小值的下標(biāo)，當(dāng)前是第幾輪，k就先代表第幾個(gè)元素的下標(biāo)，然后依次和后面的元素進(jìn)行比較，如果發(fā)現(xiàn)比k位置元素小的元素時(shí)，改變k的下標(biāo)，這樣一輪過后k代表的位置就是本輪最小的元素，和i進(jìn)行交換即可
• 如果一輪過后k==i，則說明i本來就是最小的元素，則無需交換提高性能。

5.插入排序

插入排序的思路

基本思路：

假設(shè)一個(gè)數(shù)組已經(jīng)基本有序，則這個(gè)時(shí)候插入排序就是一個(gè)不錯(cuò)的選擇。插入排序是先保證左邊元素是基本有序的，然后將后面的元素依次和左邊元素進(jìn)行比較，如果比較到一個(gè)比自己小的元素時(shí)就可以停止比較了，因?yàn)樽筮呉呀?jīng)呈現(xiàn)有序狀態(tài)，找到比自己小的元素時(shí)，就不用再往后比較了。

插入排序的代碼實(shí)現(xiàn)：

• 插入排序的輪數(shù)和冒泡排序一樣，但是i從1開始，因?yàn)槲覀兗僭O(shè)第一個(gè)元素已經(jīng)是呈現(xiàn)有序狀態(tài)了。
• 內(nèi)部循環(huán)依次從當(dāng)前位置開始，和前面元素進(jìn)行比較，如果找到了比自己小的元素，則停止比較，直接退出本輪比較，進(jìn)行下一輪比較

總結(jié)：

• 雖然三種排序法的時(shí)間復(fù)雜度都是O(N2)，但是不同的場(chǎng)景還是會(huì)有不同的性能差異。
• 冒泡排序法是性能最差的算法，正式運(yùn)用中，基本不會(huì)用冒泡排序法進(jìn)行排序。
• 選擇排序?qū)⒔粨Q次數(shù)降到最低，但是比較次數(shù)仍然很大。當(dāng)數(shù)據(jù)量小，并且交換耗時(shí)相對(duì)于比較耗時(shí)更多的情況下，選擇排序是個(gè)不錯(cuò)的選擇。
• 基本有序的情況下，插入排序是最好的選擇，但是如果數(shù)據(jù)基本逆序的情況下，插入排序的性能和冒泡排序就基本一樣了。
• 從平均情況下來看，插入排序性能會(huì)比選擇排序略好一些。

以上就是小編整理的Java經(jīng)典的八種排序算法，希望對(duì)學(xué)習(xí)Java的小伙伴有幫助

到此這篇關(guān)于Java常用的八種排序算法及代碼實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java常用排序算法及代碼實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論