?
?? 博客內(nèi)容：【數(shù)據(jù)結(jié)構(gòu)】插入排序詳細(xì)圖解（一看就懂）
?? 作??者：陳大大陳
??所屬專欄：數(shù)據(jù)結(jié)構(gòu)筆記
?? 個(gè)人簡介：一個(gè)正在努力學(xué)技術(shù)的準(zhǔn)前端，專注基礎(chǔ)和實(shí)戰(zhàn)分享 ，歡迎私信！
?? 歡迎大家：這里是CSDN，我總結(jié)知識和寫筆記的地方，喜歡的話請三連，有問題請私信 ?? ?? ??
目錄
前言引入
?插入排序的原理
插入排序源碼
詳細(xì)實(shí)例過程圖解
本章小結(jié)
前言引入
??插入排序是一種非常有意思且比較高效的排序方法，同時(shí)插入排序是希爾排序的基礎(chǔ)?。
我預(yù)備下一篇博客講解希爾排序，這一篇就先講一下插入排序。
在生活中，這種排序方法也隨處可見。
例如，我們在玩撲克牌時(shí)，總會(huì)按照插入排序的方法調(diào)整撲克牌的位置。?
玩撲克牌怎么會(huì)用到插入排序的方法呢？
當(dāng)我們拿起第二張牌時(shí)，就會(huì)下意識的與第一張牌進(jìn)行比較，如果比第一張牌小，我們就會(huì)將牌插入至第一張牌的左邊，反之就插入至右邊。
這樣邊插入邊排序，就是插入排序，插入后的序列依舊是有序的。
大家先看一下下面的原理和代碼，然后再看實(shí)例圖可能會(huì)比較好。
?插入排序的原理
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。?
我們將原數(shù)組空間看成兩個(gè)部分，前邊是有序部分，后邊是無序部分，有序部分我們默認(rèn)為它就已經(jīng)是排好序的，在尾部新加入的元素有可能會(huì)導(dǎo)致整個(gè)有序數(shù)組變得無序，因此我們需要進(jìn)行調(diào)整。
調(diào)整方式就是將新加入的元素進(jìn)行對比并往前移動(dòng)，新加入元素和它前邊的元素進(jìn)行對比，如果它比它前邊的元素小，則二者互換位置，不斷重復(fù)這個(gè)過程，直到它前邊的元素小于它才會(huì)停止，這樣一來，他就仍然是有序數(shù)組。
插入排序源碼
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int* a, int n)
{
int tmp;
int end;
for (int i = 1; i < n; i++)
{
end = i - 1;
tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
int main()
{
int a[] = { 45,67,89,12,34,5,6,8,1,2,67,99,55 };
InsertSort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
{
printf("%d ", a[i]);
}
return 0;
}
/*{ 45,45,89,12,34,5,6,8,1,2,67,99,55 };*/運(yùn)行結(jié)果
詳細(xì)實(shí)例過程圖解
就按這組數(shù)據(jù)為例，此時(shí)end處的值不大于i處的值，不用進(jìn)入循環(huán)，?a[end + 1] = tmp;不造成影響
第二次，同理，i++繼續(xù)往后走。
第三次，這次不一樣了！a[end]>a[i]，也就是a[end]大于tmp了，進(jìn)入循環(huán)。
循環(huán)一次，完成?a[end + 1] = a[end];??end--;a[end+1]=tmp;的操作。
此時(shí)end值為1，大于0，循環(huán)繼續(xù)。
循環(huán)兩次，完成?a[end + 1] = a[end];??end--;a[end+1]=tmp;的操作。
此時(shí)end值為0，等于0，循環(huán)繼續(xù)。
?
循環(huán)三次，?完成?a[end + 1] = a[end];??end--;a[end+1]=tmp;的操作。
此時(shí)end值為-1，小于0，循環(huán)結(jié)束。
第一次排序結(jié)束，下面的排序也就是比葫蘆畫瓢了，這里我就不列舉了。
本章小結(jié)
直接插入排序的特性總結(jié)：1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高2. 時(shí)間復(fù)雜度：O(N^2)3. 空間復(fù)雜度：O(1)，是一種穩(wěn)定的排序算法4. 是否穩(wěn)定：穩(wěn)定
下一篇更新希爾排序，博客里如果有問題的話，還請大佬私信我，我會(huì)修改的。文章來源：http://www.zghlxwxcb.cn/news/detail-467002.html
有問題的話請私信問我，我看到就會(huì)回的。?文章來源地址http://www.zghlxwxcb.cn/news/detail-467002.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】插入排序詳細(xì)圖解（一看就懂）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
