圖解Java經(jīng)典算法冒泡選擇插入希爾排序的原理與實(shí)現(xiàn)
一、冒泡排序
1、基本介紹
冒泡排序是重復(fù)地走訪要排序的元素,依次比較兩個(gè)相鄰的元素,如果它們的順序與自己規(guī)定的不符合,則把兩個(gè)元素的位置交換。走訪元素重復(fù)地進(jìn)行,直到?jīng)]有相鄰元素需要交換為止,完成整個(gè)排序過程。
? 算法原理
1、比較相鄰元素,如果前一個(gè)元素大于后一個(gè)元素,則交換。
2、依次向后對(duì)每一對(duì)相鄰元素做同樣的工作,直到隊(duì)列末尾,第一輪過后最大的元素就位于最后一個(gè)元素位置了。
3、重復(fù)以上步驟,直到最后一個(gè)元素位置的前一位為止(因?yàn)樽詈笠晃灰呀?jīng)排了)。
4、持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面步驟,直到第一個(gè)元素和第二個(gè)元素交換后順序?yàn)閺拇蟮叫』驈男〉酱螅判蚪Y(jié)束。
2、代碼實(shí)現(xiàn)
冒泡排序?qū)嶋H上就是兩個(gè)數(shù)兩個(gè)數(shù)的比較,每循環(huán)一次將最大或最小的數(shù)放在最后,剩下的就繼續(xù)兩兩比較。
public static void bubbleSort(int[] arr){ //中間變量,用來(lái)交換數(shù)據(jù) int temp = 0; //外層循環(huán) for (int i = 0 ; i < arr.length - 1 ; i++){ //內(nèi)層循環(huán),每次找到最大的數(shù)后放在最后,下次遍歷則會(huì)少一次,及arr.length - i - 1 for(int j = 0; j < arr.length - i - 1; j++){ //判斷大小 if(arr[j] > arr[j + 1]){ //將兩數(shù)進(jìn)行交換 temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
二、 選擇排序
1、基本介紹
首先第一次確定第一個(gè)數(shù)為最小的,然后利用for循環(huán),將第一個(gè)數(shù)后的數(shù)據(jù)遍歷一遍,找是否還有比第一個(gè)數(shù)更小的,記錄下來(lái),遍歷完畢后將第一個(gè)數(shù)與最小的數(shù)進(jìn)行交換。然后又確定第二數(shù),找第二個(gè)數(shù)以后的數(shù),是否還有比第二個(gè)數(shù)更小的,找到后與第二個(gè)數(shù)又進(jìn)行交換,重復(fù)上面即可。
以后的每次循環(huán)都是按照這種方式,直到最后兩個(gè)數(shù)排完,數(shù)據(jù)就是有序的了。
2、代碼實(shí)現(xiàn)
public static void choiceSort(int[] arr){ //用來(lái)記錄最小的數(shù) int arrData = 0; //記錄最小的數(shù)的下標(biāo) int arrindx = 0; //外層循環(huán),直到 arr.length - 1 即可 for(int i = 0; i < arr.length - 1; i++){ //首先把a(bǔ)rr[i] 當(dāng)做最小的數(shù),并記錄下標(biāo) arrData = arr[i]; arrindx = i; //內(nèi)層循環(huán),遍歷 i 以后的數(shù),找到比 arr[i] 還小的數(shù) for (int j = i + 1; j < arr.length; j++){ //找到更小的數(shù),就進(jìn)行記錄 if(arrData > arr[j]){ arrData = arr[j]; arrindx = j; } } //循環(huán)完畢,說(shuō)明找到了,最小的數(shù),與arr[i] 進(jìn)行交換即可 arr[arrindx] = arr[i]; arr[i] = arrData; } }
三、插入排序
1、基本介紹
前面我們介紹的選擇排序,找到最小的就與前面的進(jìn)行交換。而插入排序,就是將確定的數(shù)的后一位插入到前面即可。圖形介紹:
開始,id指向第一個(gè)數(shù),mid指向第二個(gè)數(shù),然后兩個(gè)數(shù)進(jìn)行比較。
此時(shí),1 比 3 小,但是3前面沒數(shù)據(jù)了,于是將1插入到3的前面,注意這里是插入,不是交換。下一步 3 比 5 小,于是不用插入。
經(jīng)過三次比較,確定了 2 的位置在 1 和 3 直接,直接將 2 插入。
又經(jīng)過四次比較,找到 0 的位置 在 1 的前面,于是將 0 插入到 1 的前面即可。
2、代碼實(shí)現(xiàn)
public static void insertSort(int[] arr){ //下標(biāo)為 0 的數(shù)是確定的,從下標(biāo)為 1 開始循環(huán) for (int i = 1; i < arr.length; i++){ // 將下標(biāo)為 i 的數(shù)暫存起來(lái) int arrData = arr[i]; //從 i - 1 開始往前循環(huán) int arrIndx = i - 1; //判斷退出的條件 大于等于0 while (arrIndx >= 0){ //如果arrData 大于 下標(biāo)為arrIndx 的數(shù),則位置找到,退出循環(huán) if (arrData > arr[arrIndx]){ break; } //沒有找到,就將前面的數(shù)往后移 arr[arrIndx + 1] = arr[arrIndx]; arrIndx--; } //找到位置后,就將暫存的數(shù)據(jù)arrData 插入到下標(biāo)為arrIndx的位置 arr[arrIndx + 1] = arrData; } }
四、希爾排序
1、基本介紹
首先將數(shù)組分為兩組,3、2、0 為一組,1、5為一組,g = arr.length / 2。
2 和 3 進(jìn)行判斷,3 比 2 大 ,然后進(jìn)行交換位置,交換后 j = j- g< 0(因?yàn)榈谝淮蔚姆譃閮山M,所以 i - 2)。所以 i++ ,j = i - g
不需要交換, 然后 j = j- g < 0 ,所以 i++ ,j = i - g
3 比 0 大 ,需要交換。然后 j = j - g > 0 , j = j - g
交換后 j = j - g < 0 , i++ > arr.length 了,第一輪結(jié)束
第二輪:在arr.length / 2的基礎(chǔ)上再除2 , 于是 g = 1 ;
然后兩兩交換,交換后 進(jìn)行j = j - g > 0 的判斷 ,不成立則 i++, j = i - g ,成立則 j = j - g ,就這樣一直循環(huán)下去。第二輪后的結(jié)果:
第二輪結(jié)束后,g / 2 = 0 結(jié)果不大于 0,所以排序結(jié)束
2、代碼實(shí)現(xiàn)(交換排序)
public static void shellSort_exchange(int[] arr){ //做中間變量,進(jìn)行數(shù)據(jù)交換 int temp = 0; // g 首先數(shù)組總長(zhǎng)除以2, 然后每次除以2 for(int g = arr.length / 2 ; g > 0 ; g /= 2){ // i 從 g 的位置開始遍歷 for(int i = g ; i < arr.length ; i++){ // j 從 i - g 的位置開始向前遍歷,j 的位置由 j - g 來(lái)決定 for(int j = i - g ; j >= 0 ; j -= g){ //判斷 下標(biāo)(j + g) 和 下標(biāo)j 位置的數(shù)的大小,然后進(jìn)行交換 if(arr[j + g] < arr[j]){ //交換即可 temp = arr[j + g]; arr[j + g] = arr[j]; arr[j] = temp; } } } } }
3、代碼實(shí)現(xiàn)(移位排序)
移位排序的思想與前面的交換排序一樣的,只是在交換數(shù)的方式上有變化。交換排序數(shù)的交換方式來(lái)自冒泡排序,而移位排序數(shù)的交換方式來(lái)自插入排序。
public static void test1(int[] arr){ //與前面一樣,開始數(shù)組長(zhǎng)度除以2 , 然后每次除以2 for(int g = arr.length / 2 ; g > 0 ; g /= 2){ // i 從 g 位置開始,每次加一 for(int i = g ; i < arr.length ; i++){ //定義 j 的位置 為 i int j = i ; //將 下標(biāo)為 i 位置的數(shù)暫存起來(lái) int temp = arr[i]; //判斷 下標(biāo)j位置的數(shù) 和 j - g 位置的數(shù),與前面一樣 if(arr[j] < arr[j - g] ){ //遍歷循環(huán) while(j - g >= 0 && temp < arr[j - g]){ //滿足條件,就移位,將前面的數(shù) (下標(biāo)j - g) 往后移 (下標(biāo)j) arr[j] = arr[j - g]; j -= g;// j 每次 -g } } //退出循環(huán)或判斷條件后,將暫存的temp (arr[i]) 賦值給 arr[j] arr[j] = temp; } } }
到此這篇關(guān)于圖解Java經(jīng)典算法冒泡選擇插入希爾排序的原理與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java冒泡排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
利用Java8 Optional類優(yōu)雅如何地解決空指針問題
這篇文章主要給大家介紹了關(guān)于如何利用Java8 Optional類優(yōu)雅解決空指針問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11異常解決SpringBoot項(xiàng)目啟動(dòng)卡住,無(wú)任何異常信息問題
這篇文章主要介紹了異常解決SpringBoot項(xiàng)目啟動(dòng)卡住,無(wú)任何異常信息問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-03-03使用Runnable實(shí)現(xiàn)數(shù)據(jù)共享
這篇文章主要為大家詳細(xì)介紹了如何使用Runnable實(shí)現(xiàn)數(shù)據(jù)共享,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-07-07JavaWeb項(xiàng)目FullCalendar日歷插件使用的示例代碼
本篇文章主要介紹了JavaWeb項(xiàng)目FullCalendar日歷插件使用的示例代碼,具有一定的參考價(jià)值,有興趣的可以了解一下2017-08-08