java排序之插入排序，插入排序分為直接插入排序和希爾排序兩種。

1.直接插入排序思想：在需要排序的一組數(shù)據(jù)中假設(shè)前該數(shù)組的前n-1（n >= 2）個(gè)數(shù)是已經(jīng)排好序的,現(xiàn)在要把第n個(gè)數(shù)插入到前面的n-1個(gè)數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)進(jìn)行，知道n等于需要排序的數(shù)組的長(zhǎng)度時(shí)。就實(shí)現(xiàn)了該數(shù)組的直接插入排序。

代碼如下：

????/**

?*?

?* @param a 需要排序的數(shù)組

?*/

public static void simpleSort(int[] a){

for(int i = 1;i<a.length;i++){//外層for循環(huán)從1開(kāi)始

int temp = a[i];

int j = i-1;

for(;j>=0 && temp < a[j];j--){

a[j+1] = a[j];

}

a[j+1] = temp;

}

}

//代碼解釋：

例如：需要排序的數(shù)組int[] a = {49,38,65,97,76,13,27};

第一次執(zhí)行該方法執(zhí)行for循環(huán)。

????i=1，temp=38，j=0，a[j]= 49 38 < 49 滿足for(;j>=0 && temp < a[j];j--)條件

????執(zhí)行a[j+1] = a[j]即a[1] = a[0] 執(zhí)行后數(shù)組為a=[49,49,65,97,76,13,27]?

執(zhí)行j--，執(zhí)行后j=-1 跳出內(nèi)部for循環(huán)

執(zhí)行a[j+1] = temp; j=-1 因此 a[0] = 38;

完成第一次循環(huán)后 數(shù)組a=[38,49,65,97,76,13,27]

?

第二次執(zhí)行外部循環(huán)

i=2，temp=65，j=1，a[j]=49 65 > 49 不滿足內(nèi)部for循環(huán)條件直接跳出

執(zhí)行 a[j+1] = temp; 即a[2]=65

完成第二次循環(huán)后 數(shù)組a=[38,49,65,97,76,13,27]

?

第三次外部循環(huán)

i=3，temp=97，j=2，a[j]=65 97 > 65 不滿足內(nèi)部for循環(huán)條件直接跳出

執(zhí)行a[j+1] = temp;即a[3] = 97

完成第三次循環(huán)后 數(shù)組a=[38,49,65,97,76,13,27]

?

第四次外部循環(huán)

i=4,temp=76,j=3,a[j]=97 76 < 97 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1] = a[j];即a[4] = a[3] 執(zhí)行后數(shù)組為a=[38,49,65,97,97,13,27]

執(zhí)行j--，執(zhí)行后j=2 a[j]=65 76 > 65 不滿足繼續(xù)執(zhí)行內(nèi)部for循環(huán)的條件 直接跳出

執(zhí)行a[j+1] = temp;即a[3] = 76

完成第四次循環(huán)后 數(shù)組a=[38,49,65,76,97,13,27]

?

第五次外部循環(huán)

i=5,temp=13,j=4,a[j]=97 13 < 97 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1] = a[j];即a[5] = a[4] 執(zhí)行后數(shù)組為a=[38,49,65,76,97,97,27]

執(zhí)行j--，執(zhí)行后j=3，a[j]=76 13 < 76 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1] = a[j];即a[4] = a[3] 執(zhí)行后數(shù)組為a=[38,49,65,76,76,97,27]

執(zhí)行j--，執(zhí)行后j=2 a[j]=65 13 < 65 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1]=a[j];即a[3] = a[2] 執(zhí)行后數(shù)組a=[38,49,65,65,76,97,27]

執(zhí)行j--，執(zhí)行后j=1 a[j]=49 13 < 49 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1]=a[j];即a[2]=a[1] 執(zhí)行后數(shù)組為a=[38,49,49,65,76,97,27]

執(zhí)行j--，執(zhí)行后j=0，a[j] = 38,13 < 38 滿足內(nèi)部for循環(huán)條件

執(zhí)行a[j+1]=a[j];即a[1] = a[0] 執(zhí)行后數(shù)組為a=[38,38,49,65,76,97,27]

執(zhí)行j--，執(zhí)行后j=-1，不滿足內(nèi)部for循環(huán)條件跳出循環(huán)

執(zhí)行a[j+1] = temp;即a[0]=13 執(zhí)行后數(shù)組a=[13,38,49,65,76,97,27]

完成第五次循環(huán) 。

依次循環(huán)直到跳出外部for循環(huán)整個(gè)數(shù)組排序完成。

?

2.希爾排序法

?2.1實(shí)現(xiàn)思想 ??

? 在直接插入排序算法中，每次插入一個(gè)數(shù)。使有序序列 只增加幾個(gè)節(jié)點(diǎn)，而且對(duì)插入下一個(gè)數(shù)沒(méi)有提供任何幫助。如果比較相隔較遠(yuǎn)（稱為增量）的兩個(gè)數(shù)，使得數(shù)移動(dòng)時(shí)能跨過(guò)多個(gè)數(shù)，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.Shell于1959年以他的名字命名的排序算法中實(shí)現(xiàn)了這一思想，這塊相關(guān)的java教程比較少。算法先將要排序的一組數(shù)按照某個(gè)增量d分成若干組，每組中元素的下標(biāo)相差d。對(duì)每組中全部元素進(jìn)行排序，然后在用一個(gè)較小的分量（較小的分量一般取當(dāng)前分量的一半d/2）對(duì)排序后的的 整個(gè)數(shù)組進(jìn)行分組。再對(duì)每組進(jìn)行排序。當(dāng)增量d=1時(shí)，整個(gè)要排序的數(shù)組本分成一個(gè)數(shù)組，然后進(jìn)行排序，排序即可完成。

?2.2歷史背景

? 直接插入排序它的效率在某些時(shí)候是很高的，比如我們的元素本身就是基本有序的，我們只需要少量的插入操作，就可以完成整個(gè)數(shù)組的排序工作。此時(shí)直接插入很高效。還有就是數(shù)據(jù)比較少時(shí)，直接插入的優(yōu)勢(shì)也比較明顯。可問(wèn)題在于兩個(gè)條件本身過(guò)于苛刻，現(xiàn)實(shí)中數(shù)據(jù)少和基本有序都屬于特殊情況。有條件當(dāng)然是好的，條件不存在我們創(chuàng)造條件也要去做，于是科學(xué)家D.L.Shell研究出一種排序算法，對(duì)直接插入排序改進(jìn)后可以提高效率。

? 如何然待排序的數(shù)據(jù)少呢？很容易想到就是將原本有大量數(shù)據(jù)的數(shù)組進(jìn)行分組，分割成若干個(gè)子序列，此時(shí)每個(gè)子序列的數(shù)據(jù)就比較少。然后在這些子序列內(nèi)分別進(jìn)行直接插入排序，當(dāng)整個(gè)序列都基本有序時(shí)，在對(duì)全體記錄進(jìn)行一次直接插入排序。問(wèn)題其實(shí)也就在這里，我們分隔待排序數(shù)組的目的就是為了減少數(shù)據(jù)的量，對(duì)每個(gè)子序列進(jìn)行直接插入排序就是為了讓整個(gè)數(shù)組基本有序。

??例如數(shù)組a=[9,1,5,8,3,7,2,4,6]現(xiàn)在將他按前后順序分為三組a1=[9,1,5]，a2=[8,3,7],

a3=[2,4,6],將三個(gè)子序列a1,a2,a3排序后重新組合在一起后a=[1,5,9,3,7,8,2,4,6],此時(shí)這個(gè)數(shù)組還是雜亂無(wú)序的，根本談不上基本有序，要排序還是直接重來(lái)一遍插入排序。這樣做只是瞎子戴眼鏡多余的圈圈，毫無(wú)用處，所謂基本有序不是局部有序而是小的數(shù)據(jù)基本在前面，大的的數(shù)據(jù)基本在后面，不大不小的數(shù)據(jù)基本在中間，因此我們會(huì)發(fā)現(xiàn)將一組需要排序的數(shù)據(jù)按照先后順序分組排序后滿足不了我們的要求。所以我們需要采取跳躍分割的策略：將相距某個(gè)“增量”的數(shù)據(jù)組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行插入排序后得到的結(jié)果是一個(gè)基本有序的數(shù)組而不是一個(gè)局部有序的數(shù)組。

? ?代碼實(shí)現(xiàn)：

public static void shellSort(int[] a){

int j;

int len = a.length;

for(int d = len >> 1;d > 0;d = d >> 1 ){

for(int i = d;i<len;i++){

int temp = a[i];

for(j = i; j >= d && temp < a[j-d]; j -= d){

a[j] = a[j-d];

}

a[j] = temp;

}

}

}

轉(zhuǎn)載于:https://www.cnblogs.com/jinshiyill/p/5226474.html

總結(jié)

以上是生活随笔為你收集整理的java排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。