欧美成人午夜免费全部完,亚洲午夜福利精品久久,а√最新版在线天堂,另类亚洲综合区图片小说区,亚洲欧美日韩精品色xxx

扣丁學(xué)堂Java培訓(xùn)數(shù)據(jù)結(jié)構(gòu)與算法之基本排序詳解

2018-05-30 13:46:40 1132瀏覽

今天扣丁學(xué)堂給大家詳細(xì)介紹一下關(guān)于很多人對(duì)于數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)和算法沒(méi)有全面的認(rèn)知和理解，首先經(jīng)典的排序算法有八種，下面我們一起來(lái)看一下關(guān)于扣丁學(xué)堂Java培訓(xùn)數(shù)據(jù)結(jié)構(gòu)與算法之基本排序詳解吧。

冒泡排序

選擇排序

插入排序

歸并排序

希爾排序

快速排序

堆排序

基數(shù)排序

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

冒泡排序

基本思路：

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

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

圖解：

假設(shè)對(duì)5個(gè)元素進(jìn)行冒牌排序，先準(zhǔn)備5個(gè)隨機(jī)元素：

1）第一輪中，將第一個(gè)元素（10）與相鄰的元素（20）進(jìn)行比較，因?yàn)?0比10大所以無(wú)需進(jìn)行交換。再將第二個(gè)元素（20）與相鄰的元素（5）比較，因?yàn)?0比5大，所以需要往上‘冒’，因此需要與5進(jìn)行交換

接著將第三個(gè)元素（20）與相鄰的元素進(jìn)行比較，這樣經(jīng)過(guò)與14和1的比較之后，因?yàn)?0最大，所以被冒到了最后的位置

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)整體排序

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

首先通過(guò)一個(gè)外層的for循環(huán)確定比較的輪數(shù)，循環(huán)元素?cái)?shù)量-1輪。

內(nèi)部通過(guò)一個(gè)for循環(huán)實(shí)現(xiàn)每輪的兩兩元素比較的效果。每輪需要比較的次數(shù)都會(huì)比上一輪減少一次，通過(guò)j

元素兩兩比較通過(guò)array[j]>array[j+1]來(lái)實(shí)現(xiàn)。

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

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

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

選擇排序

基本思路：

選擇排序和冒泡排序不同，選擇排序會(huì)通過(guò)一輪比較，選出最小的那個(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)，這樣一輪過(guò)后k代表的位置就是本輪最小的元素，和i進(jìn)行交換即可

如果一輪過(guò)后k==i，則說(shuō)明i本來(lái)就是最小的元素，則無(wú)需交換提高性能。

插入排序

插入排序的思路

基本思路

假設(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ò)的選擇?；居行虻那闆r下，插入排序是最好的選擇，但是如果數(shù)據(jù)基本逆序的情況下，插入排序的性能和冒泡排序就基本一樣了。從平均情況下來(lái)看，插入排序性能會(huì)比選擇排序略好一些。

以上就是扣丁學(xué)堂Java在線學(xué)習(xí)小編給大家分享的Java使用默認(rèn)瀏覽器打開指定URL的方法(兩種方法)，希望對(duì)小伙伴們有所幫助，想要了解更多內(nèi)容的小伙伴可以登錄扣丁學(xué)堂官網(wǎng)查詢。扣丁學(xué)堂是專業(yè)的Java培訓(xùn)機(jī)構(gòu)，不僅有專業(yè)的老師和與時(shí)俱進(jìn)的課程體系，還有大量的Java視頻教程供學(xué)員掛看學(xué)習(xí)哦。Java技術(shù)交流群：670348138

【關(guān)注微信公眾號(hào)獲取更多學(xué)習(xí)資料】

查看更多關(guān)于“Java開發(fā)資訊”的相關(guān)文章>>