這次直入主題，我今天要復(fù)習(xí)的是插入排序悯周！插入排序分為“直接插入”和“Shell排序”，Shell排序就是希爾排序陪竿，可以看做是直接插入排序從成熟體進(jìn)化為完全體~
好的直接來(lái)看插入排序：
直接插入排序
我們先說(shuō)一下插入排序的原理：
通過(guò)對(duì)未排序的數(shù)據(jù)執(zhí)行逐個(gè)插入到合適的位置完成排序工作禽翼。
- 1.首先對(duì)數(shù)組前兩個(gè)數(shù)據(jù)進(jìn)行從小到大排序
- 2.將第三個(gè)數(shù)據(jù)與排好序的兩個(gè)數(shù)據(jù)比較，插入合適的位置族跛。
- 3.第四個(gè)同樣方式插入到他們?nèi)齻€(gè)中闰挡。
- 4.不斷重復(fù)，直到結(jié)束礁哄。
- 時(shí)間復(fù)雜度： 平均：O(n^2) 最佳：O(n) 最壞：O(n^2)
- 空間復(fù)雜度： O(1)
- 穩(wěn)定性： 穩(wěn)定
這個(gè)聽(tīng)起來(lái)比冒泡難一些长酗，但是其實(shí)想象力豐富一些，就會(huì)覺(jué)得這個(gè)這個(gè)很簡(jiǎn)單~給個(gè)圖片就懂了桐绒！
我又去百科盜圖了：
圖片的簡(jiǎn)單明了吧夺脾？就是從第二個(gè)值開(kāi)始依次去取之拨。然后每次都比較，然后把每次取的數(shù)字咧叭，放到該放的位置上蚀乔。
直接看代碼吧：手敲代碼：
/**
* Created by AceCream on 2017/3/20.
*
* 插入排序（Insertion Sort）
* 原理：通過(guò)對(duì)未排序的數(shù)據(jù)執(zhí)行逐個(gè)插入到合適的位置完成排序工作。
* 1.首先對(duì)數(shù)組前兩個(gè)數(shù)據(jù)進(jìn)行從小到大排序
* 2.將第三個(gè)數(shù)據(jù)與排好序的兩個(gè)數(shù)據(jù)比較菲茬，插入合適的位置吉挣。
* 3.第四個(gè)同樣方式插入到他們?nèi)齻€(gè)中。
* 4.不斷重復(fù)婉弹，直到結(jié)束袱讹。
*
* 時(shí)間復(fù)雜度： 平均：O(n^2) 最佳：O(n) 最壞：O(n^2)
* 空間復(fù)雜度： O(1)
* 穩(wěn)定性： 穩(wěn)定
*
*/
public class InsertSort {
public static void main(String[] args) {
int value[] = {12,15,9,20,6,31,24};
InsertSort insertSort = new InsertSort();
insertSort.insertSort(value);
System.out.print("最終結(jié)果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
private void insertSort(int[] value) {
//temp值待命
int temp;
for (int i=1;i<value.length;i++){
//從第二個(gè)數(shù)據(jù)開(kāi)始取 每輪的檢測(cè)數(shù)據(jù)都先放temp里
temp = value[i];
int j = i-1;
while (j>=0 && temp<value[j]){
//如果比較的值，比temp大酪惭，就讓這個(gè)值往后去沪饺。temp繼續(xù)比較。佩脊。蛙粘。碰到比它小的，就在其后面落下（后面這句是循環(huán)外放下的）
value[j+1]=value[j];
j--;
}
//沒(méi)有比它小的就放回去威彰，有的話(huà)就放到應(yīng)該在的位置
value[j+1]=temp;
}
}
}
我都注釋的比較詳細(xì)了~雖然我自己也總忘這個(gè)排序出牧。
好的吃完甜點(diǎn)，我們開(kāi)始今天的主菜——Shell排序
希爾排序
希爾排序是理論上效率最高的排序歇盼。但是舔痕！但是僅僅是理論上，因?yàn)樵趯?shí)踐中的使用豹缀，希爾排序還是被快排擊敗了伯复，兩種排序都不太穩(wěn)定，但是整體的試驗(yàn)中邢笙，快排還是略勝一籌~
希爾排序啸如，也叫做縮小增量排序，其執(zhí)行方式氮惯，我個(gè)人覺(jué)得還是很變態(tài)的叮雳。
還是看步驟吧：
- 1.將n個(gè)元素的數(shù)組分為n/2個(gè)數(shù)字序列：第一個(gè)數(shù)據(jù)和第n/2+1個(gè)數(shù)據(jù)為一對(duì)...
- 2.一次循環(huán)使每個(gè)序列對(duì)排好
- 3.變?yōu)閚/4個(gè)序列，再次排序妇汗。
- 4.不斷重復(fù)帘不，周而復(fù)始，隨著序列變?yōu)?杨箭，排序完成
看這個(gè)圖寞焙，應(yīng)該是可以理解的，它是分來(lái)，然后一一對(duì)應(yīng)捣郊，然后比較辽狈，單獨(dú)排序，直到最后模她，排列整齊稻艰。。侈净。
當(dāng)初覺(jué)得這個(gè)思想好強(qiáng)尊勿！但是！我覺(jué)得簡(jiǎn)單了解其原理就足夠了畜侦。當(dāng)然元扔，想手敲也是可以的，但覺(jué)得必要性不是那么強(qiáng)旋膳，因?yàn)閼?yīng)用情況下澎语，我寧可選擇快排。
/**
* Created by AceCream on 2017/3/22.
* 希爾排序（ShellSort）
* 希爾排序效率很高验懊！所以也是很常用的一種排序擅羞。
* 基于插入排序的思想：縮小增量排序
* 步驟：
* 1.將n個(gè)元素的數(shù)組分為n/2個(gè)數(shù)字序列：第一個(gè)數(shù)據(jù)和第n/2+1個(gè)數(shù)據(jù)為一對(duì)...
* 2.一次循環(huán)使每個(gè)序列對(duì)排好
* 3.變?yōu)閚/4個(gè)序列，再次排序义图。
* 4.不斷重復(fù)减俏，周而復(fù)始，隨著序列變?yōu)?碱工，排序完成
*
* 時(shí)間復(fù)雜度： 平均：O(n^1.3) 最佳：O(n) 最壞：O(n^2)
* 空間復(fù)雜度： O(1)
* 穩(wěn)定性： 不穩(wěn)定
*
*/
public class ShellSort {
public static void shellSort(int a[]){
int gap;
int lenth = a.length;
for (gap=lenth/2;gap>0;gap/=2){ //從數(shù)組的第gap個(gè)元素開(kāi)始 分出來(lái)循環(huán)幾次
for (int i=0;i<gap;i++){ //分出來(lái)有多少組
//直接插入排序
for (int j=i+gap;j<lenth;j+=gap){
if (a[j]<a[j-gap]){
int temp = a[j];
int k = j-gap;
while (k>=0&&temp<a[k]){
a[k+gap]=a[k];
k -= gap;
}
a[k+gap]=temp;
}
}
}
}
}
public static void main(String[] args) {
int value[] = {49,27,46,55,4,13,38,65,97,26};
shellSort(value);
System.out.print("最終結(jié)果 ");
for (int result : value) {
System.out.print(result+" ");
}
}
}
這一次我沒(méi)有選擇在線(xiàn)手敲娃承，私下每次我需要使用的時(shí)候我會(huì)回來(lái)看看畢竟學(xué)習(xí)不是背誦，最主要的是：了解其思想怕篷！
