圖解Java經(jīng)典算法希爾排序的原理與實(shí)現(xiàn)
希爾排序
希爾排序時(shí)插入排序的一種,也稱縮小增量排序,是直接插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
算法思想
希爾排序是把記錄按下標(biāo)的一定增量分組,對(duì)每組使用直接插入排序算法排序,隨著增量逐漸減少,每組包含的數(shù)越來(lái)越多當(dāng)增量減至1時(shí),整個(gè)序列恰好被分成一組,算法完成。
我們以增序排序?yàn)槔柵判蚧静襟E:選擇初始增量gap=length/2
,縮小增量繼續(xù)以gap=gap/2
的方式進(jìn)行,直到增量gap=1
為止,增量的每次變化都會(huì)將原始序列劃分為若干組,分別對(duì)每一組進(jìn)行插入排序,每一次通過(guò)增量劃分組進(jìn)行插入排序宏觀上小的數(shù)移到了前面,大的數(shù)移到了后面,最后增量gap=1進(jìn)行插入排序后就是最終的有序序列。下面以圖解的方式詳細(xì)介紹希爾排序算法的整個(gè)流程。
圖解
代碼實(shí)現(xiàn)(Java)
public class ShellSort { public static void main(String[] args){ int[] array = {86,11,54,34,53,12,45,81,19,65}; int gap = array.length; while (true) { gap /= 2; //增量每次減半 for (int i = 0; i < gap; i++) { for (int j = i + gap; j < array.length; j += gap) {//這個(gè)循環(huán)里其實(shí)就是一個(gè)插入排序 int k = j - gap; while (k >= 0 && array[k] > array[k+gap]) { int temp = array[k]; array[k] = array[k+gap]; array[k + gap] = temp; k -= gap; } } } if (gap == 1) break; } System.out.println("排序結(jié)果:"); for(int i=0;i<array.length;i++){ System.out.print(array[i]+" "); } } } //排序前:{86,11,54,34,53,12,45,81,19,65} //排序后:{11,12,19,34,45,53,54,65,81,86}
到此這篇關(guān)于圖解Java經(jīng)典算法希爾排序的原理與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java希爾排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
IDEA 2020.1打開(kāi)時(shí)閃退的問(wèn)題及解決方法(完美解決方法)
這篇文章主要介紹了IDEA 2020.1打開(kāi)時(shí)閃退問(wèn)題及解決方法,本文給大家分享我的處理方案,對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-04-04SpringBoot使用spring.config.import多種方式導(dǎo)入配置文件
本文主要介紹了SpringBoot使用spring.config.import多種方式導(dǎo)入配置文件,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05JVM自定義類加載器在代碼擴(kuò)展性實(shí)踐分享
這篇文章主要介紹了JVM自定義類加載器在代碼擴(kuò)展性實(shí)踐分享,一個(gè)類型從被加載到虛擬機(jī)內(nèi)存中開(kāi)始,到卸載出內(nèi)存為止,它的整個(gè)生命周期將會(huì)經(jīng)歷加載、驗(yàn)證、準(zhǔn)備、解析、初始化 、使用和卸載七個(gè)階段,其中驗(yàn)證、準(zhǔn)備、解析三個(gè)部分統(tǒng)稱為連接2022-06-06深入淺出重構(gòu)Mybatis與Spring集成的SqlSessionFactoryBean(上)
通常來(lái)講,重構(gòu)是指不改變功能的情況下優(yōu)化代碼,但本文所說(shuō)的重構(gòu)也包括了添加功能。這篇文章主要介紹了重構(gòu)Mybatis與Spring集成的SqlSessionFactoryBean(上)的相關(guān)資料,需要的朋友可以參考下2016-11-11Java使用IOC控制反轉(zhuǎn)的三種設(shè)計(jì)模式詳解
這篇文章主要為大家詳細(xì)介紹了Java使用IOC控制反轉(zhuǎn)的三種設(shè)計(jì)模式,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-10-10在SpringMVC框架下實(shí)現(xiàn)文件的上傳和下載示例
本篇文章主要介紹了在SpringMVC框架下實(shí)現(xiàn)文件的上傳和下載示例,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。2017-02-02關(guān)于Java的ArrayList數(shù)組自動(dòng)擴(kuò)容機(jī)制
這篇文章主要介紹了關(guān)于Java的ArrayList數(shù)組自動(dòng)擴(kuò)容機(jī)制,ArrayList底層是基于數(shù)組實(shí)現(xiàn)的,是一個(gè)動(dòng)態(tài)數(shù)組,自動(dòng)擴(kuò)容,不是線程安全的,只能用在單線程環(huán)境下,需要的朋友可以參考下2023-05-05