這次直入主題，我今天要復(fù)習(xí)的是插入排序！插入排序分為“直接插入”和“Shell排序”，Shell排序就是希爾排序，可以看做是直接插入排序從成熟體進(jìn)化為完全體~
好的直接來看插入排序：
直接插入排序
我們先說一下插入排序的原理：
通過對(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è)聽起來比冒泡難一些，但是其實(shí)想象力豐富一些，就會(huì)覺得這個(gè)這個(gè)很簡單~給個(gè)圖片就懂了！
我又去百科盜圖了：
圖片的簡單明了吧？就是從第二個(gè)值開始依次去取。然后每次都比較，然后把每次取的數(shù)字，放到該放的位置上。
直接看代碼吧：手敲代碼：
/**
* Created by AceCream on 2017/3/20.
*
* 插入排序（Insertion Sort）
* 原理：通過對(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ù)開始取 每輪的檢測數(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--;
}
//沒有比它小的就放回去，有的話就放到應(yīng)該在的位置
value[j+1]=temp;
}
}
}
我都注釋的比較詳細(xì)了~雖然我自己也總忘這個(gè)排序。
好的吃完甜點(diǎn)，我們開始今天的主菜——Shell排序
希爾排序
希爾排序是理論上效率最高的排序。但是！但是僅僅是理論上，因?yàn)樵趯?shí)踐中的使用，希爾排序還是被快排擊敗了，兩種排序都不太穩(wěn)定，但是整體的試驗(yàn)中，快排還是略勝一籌~
希爾排序，也叫做縮小增量排序，其執(zhí)行方式，我個(gè)人覺得還是很變態(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)該是可以理解的，它是分來，然后一一對(duì)應(yīng)，然后比較，單獨(dú)排序，直到最后，排列整齊。。。
當(dāng)初覺得這個(gè)思想好強(qiáng)！但是！我覺得簡單了解其原理就足夠了。當(dāng)然，想手敲也是可以的，但覺得必要性不是那么強(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è)元素開始 分出來循環(huán)幾次
for (int i=0;i<gap;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+" ");
}
}
}
這一次我沒有選擇在線手敲，私下每次我需要使用的時(shí)候我會(huì)回來看看畢竟學(xué)習(xí)不是背誦，最主要的是：了解其思想！
