插入排序是一種簡(jiǎn)單直觀的排序算法堪置。它的工作原理非常類似于我們抓撲克牌沐绒。
對(duì)于未排序數(shù)據(jù)(右手抓到的牌)犁柜，在已排序序列(左手已經(jīng)排好序的手牌)中從后向前掃描，找到相應(yīng)位置并插入圾笨。
插入排序在實(shí)現(xiàn)上教馆，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中擂达，需要反復(fù)把已排序元素逐步向后挪位土铺，為最新元素提供插入空間。
插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用板鬓。但是悲敷，如果需要排序的數(shù)據(jù)量很小，比如量級(jí)小于千俭令，那么插入排序還是一個(gè)不錯(cuò)的選擇后德。 插入排序在工業(yè)級(jí)庫(kù)中也有著廣泛的應(yīng)用，在STL的sort算法和stdlib的qsort算法中抄腔，都將插入排序作為快速排序的補(bǔ)充瓢湃，用于少量元素的排序（通常為8個(gè)或以下）
具體算法描述如下：
從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素赫蛇，在已經(jīng)排序的元素序列中從后向前掃描
如果該元素（已排序）大于新元素绵患，將該元素移到下一位置
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
// 分類 ------------- 內(nèi)部比較排序
// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
// 最差時(shí)間復(fù)雜度 ---- 最壞情況為輸入序列是降序排列的,此時(shí)時(shí)間復(fù)雜度O(n^2)
// 最優(yōu)時(shí)間復(fù)雜度 ---- 最好情況為輸入序列是升序排列的,此時(shí)時(shí)間復(fù)雜度O(n)
// 平均時(shí)間復(fù)雜度 ---- O(n^2)
// 所需輔助空間 ------ O(1)
// 穩(wěn)定性 ------------ 穩(wěn)定
#include
usingnamespacestd;
intmain()
{
intA[] = {6,5,3,1,8,7,2,4};//從小到大插入排序
intn =sizeof(A) /sizeof(int);
inti, j, get;
for(i =1; i < n; i++)//類似抓撲克牌排序
{
get = A[i];//右手抓到一張撲克牌
j = i -1;//拿在左手上的牌總是排序好的
while(j >=0&& A[j] > get)//將抓到的牌與手牌從右向左進(jìn)行比較
{
A[j +1] = A[j];//如果該手牌比抓到的牌大,就將其右移
j--;
}
A[j +1] = get;//直到該手牌比抓到的牌小(或二者相等),將抓到的牌插入到該手牌右邊(相等元素的相對(duì)次序未變,所以插入排序是穩(wěn)定的)
}
printf("插入排序結(jié)果：");
for(i =0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return0;
}
