直接插入排序
前言：在博客寫這些文章的目的用于記錄所學(xué)踪央，怕以后忘了来涨，如果哪里寫的不對歡迎指正屈梁，謝謝Ｑ渭睢！
學(xué)習(xí)目標(biāo)：掌握直接插入排序算法的原理和思想
一玉锌、前提知識(shí)
??排序算法概念名挥、時(shí)間復(fù)雜度≈魇兀可前往此網(wǎng)址 排序算法學(xué)習(xí)01_算法基礎(chǔ)介紹閱讀
二禀倔、直接插入排序介紹
??直接插入排序是屬于插入排序中的一種簡單的排序，它通過抽象兩個(gè)序列参淫，一個(gè)為正在排序的序列稱之為有序序列蹋艺，一個(gè)為未排序序列。
??每次從未排序序列中取值放入有序序列黄刚，來完成排序捎谨，就像抽取撲克牌一樣
三、直接插入排序工作原理
??構(gòu)建一個(gè)有序序列，接著取一個(gè)未排序序列中第一個(gè)元素涛救，然后依次從后往前掃描有序序列中的符合條件的值進(jìn)行比較畏邢，最終找到指定位置插入，成為一個(gè)有序序列中的值检吆。然后繼續(xù)判斷未排序序列中的值
?四舒萎、直接插入排序設(shè)計(jì)思路
1.根據(jù)工作原理要構(gòu)建一個(gè)有序序列
- 所說構(gòu)建，并不是真的再創(chuàng)建一個(gè)序列去接收蹭沛，而是找已排序好的序列范圍臂寝，然后剩余序列就可以慢慢進(jìn)去比較。那我們就要先給出一個(gè)有序序列摊灭，則選擇數(shù)列的第一位當(dāng)成一個(gè)有序序列
2.未排序序列中的元素咆贬，進(jìn)入有序序列中的過程
我們知道首先要保存待進(jìn)入元素，然后從后到前掃描帚呼，到達(dá)目標(biāo)位置執(zhí)行插入掏缎。但是你要知道我們此時(shí)只有一個(gè)數(shù)組，如何往有序列表a[0] 和 a[1]之中插入元素呢煤杀？
-
假設(shè)上面圖片眷蜈，正是我們要排序的數(shù)列，要讓2插入1和3之間沈自，怎么做酌儒？可以這樣實(shí)現(xiàn)：
- 每次掃描元素，發(fā)現(xiàn)符合條件枯途，則讓該有序數(shù)列往后移今豆。
- 比如本來有序數(shù)列【排序?yàn)檫f增】為： { 1，3柔袁，5 }呆躲，待插入元素為2，從后往前遍歷有序序列捶索，看到元素5時(shí)符合條件插掂，那么讓元素5往后移，此時(shí)元素5將覆蓋元素2腥例，也就是在數(shù)組中a[3] = a[2]辅甥。然后原本a[2]這個(gè)位置就可以決定是否插入，進(jìn)行判斷
在這里插入圖片描述
五燎竖、直接插入排序算法代碼實(shí)現(xiàn)
要求對以下這個(gè)數(shù)列進(jìn)行遞增排序：{3璃弄，2，5构回，1夏块，7疏咐，9，8}
package com.migu.sortingAlgorithm;
import java.util.Arrays;
/**
* 直接插入排序
*/
public class DirectInsertionSort {
public static void main(String[] args) {
int a[] = {3,2,5,1,7,9,8};
// 數(shù)列第一位已為有序序列脐供，則從下一位開始判斷是否選擇插入
for(int i = 1;i < a.length;i++){
int insertVal = a[i]; // 保存待插入的值【根據(jù)設(shè)計(jì)思路第一點(diǎn)】
int insertIndex = i-1; // 從有序序列最后一位開始判斷浑塞，也就是待插入值的前一位索引，該索引往前肯定都是已排序好的【根據(jù)設(shè)計(jì)思路第一點(diǎn)】
// 由于要求遞增政己，那么就待插入元素小于有序列表中的值時(shí)酌壕，有序列表值就執(zhí)行后移動(dòng)作。然后需要注意數(shù)組索引不能越界
while (insertIndex >=0 && insertVal < a[insertIndex]){
// 【根據(jù)設(shè)計(jì)思路第二點(diǎn)】
a[insertIndex+1] = a[insertIndex]; // 此舉將覆蓋待插入的值歇由，但我們已經(jīng)提前保存了
insertIndex--; // 從后往前遍歷
}
// while循結(jié)束inertIndex是還會(huì)再--的卵牍，所以對其+1。然后保存待插入的值
a[insertIndex+1] = insertVal;
}
System.out.println(Arrays.toString(a)); // 調(diào)用工具類輸出
}
}
六沦泌、時(shí)間復(fù)雜度分析
??討論一個(gè)算法的時(shí)間復(fù)雜度糊昙，一般都是看最壞的情況： 簡單選擇排序算法的時(shí)間復(fù)雜度為O(n^2)。更多特殊情況請參考其他書籍或博客
七赦肃、總結(jié)
??直接插入排序算法，不像冒泡排序和簡單選擇排序公浪，每完成一次排序都會(huì)在數(shù)列某個(gè)位置最終確定元素他宛。
??直接插入排序不需要重復(fù)走訪所有元素，每進(jìn)行一次排序只在有序序列中走訪并對數(shù)組上元素進(jìn)行移動(dòng)欠气。性能比冒泡排序好比簡單選擇排序差點(diǎn)
??缺點(diǎn)就是比如要做遞增時(shí)厅各，待添加元素是在有序序列中最小的，那么就要在數(shù)組上移動(dòng)大量數(shù)據(jù)预柒，極耗時(shí)間队塘。
