插入排序有2種，分別是直接插入排序和希爾排序。
1.直接插入排序：從還沒排序的數(shù)組里取出一個(gè)數(shù)，插入到已排序的數(shù)組里。
這里有一個(gè)未排序的數(shù)組:
那么具體的排序升序過程(從待排序數(shù)組里取出索引下標(biāo)從1開始，因?yàn)槌跏紩r(shí)排好序的數(shù)組沒有數(shù)字，那么下標(biāo)是0的數(shù)字就直接放入排好序的數(shù)組里):
第1趟：從未排序的數(shù)組取出第一個(gè)的數(shù)字4，4比1大，直接插入排好序的數(shù)組里；
第2趟：再從未排序的數(shù)組取出第一個(gè)的數(shù)字3，在已排好序的數(shù)組里從后往前找，找到一個(gè)比3小的數(shù)(數(shù)字1)，并插入到數(shù)字1的后面；
...
如此重復(fù)插入的過程直到排好序。
具體實(shí)現(xiàn)代碼如下：
時(shí)間復(fù)雜度：O(n^2)；
空間復(fù)雜度:只用到一個(gè)臨時(shí)空間，所以空間復(fù)雜度O(1)；
2.希爾排序：希爾排序根據(jù)增量d(看情況設(shè)置)將待排序的數(shù)組分組，每組進(jìn)行直接插入排序，每次分組排序后，d=d/2，重復(fù)分組排序數(shù)組，直到d=0結(jié)束排序。具體排序：
d=3
第1組數(shù)據(jù)：1 6 7 排序后：1 6 7
第2組數(shù)據(jù)：4 5 排序后：4 5
第3組數(shù)據(jù)：3 2 排序后：2 3
d=1
第1組數(shù)據(jù)：1 2 3 4 5 6 7 排序后：1 2 3 4 5 6 7
d=0,結(jié)束排序。
具體代碼實(shí)現(xiàn):
時(shí)間復(fù)雜度：不確定，取決于增量d的值；
空間復(fù)雜度:只用到一個(gè)臨時(shí)空間，所以空間復(fù)雜度O(1)；
其實(shí)希爾排序是直接插入排序的升級(jí)版，所以整體來看，只要思路清晰，其實(shí)插入排序并不難。
