插入排序的演算法和分析

『壹』 插入排序的演算法

排序演算法在編程領域中起著舉足輕重的作用，在目標檢索、機器學習、數值計算、圖像處理等領域有著廣泛地應用。為了追本溯源，公眾號特推出常用經典排序演算法系列推文，讓小夥伴們深入了解排序演算法的實現原理，同時也提升matlab編程能力。
插入排序演算法，它是將無序序列分成兩部分，一部分為假設已經排列完成的序列，另一部分為餘下序列，將餘下序列中的元素取出插入到已排列完成的序列中，依次比較確定插入位置，下面就一起來看看該算的實現原理吧。
插入排序演算法實現過程(以升序排列為例)：
對於長度為N的無序數組A，假定序列A(1)為排列完成的序列K，將A(2)與A(1)作比較，如果A(2)<A(1)，則兩者交換，否則保持不變，即完成序列K的元素添加；將A(3)與A(2)比較，如果A(2)<A(3)，則保持不變，否則兩者交換，繼續將A(3)與A(1)比較，如果A(3)>A(1)，則兩者交換，否則保持不變；以此類推，將餘下序列中的元素取出插入到序列K中，從序列K尾部往首部進行比較，直至完成所有元素的插入。

matlab代碼
主程序：main.m

format short;
clc;clear;
A = round(rand(1,8),2);
nA = InsertSort(A);
disp(['原始序列：',num2str(A)]);
disp(['插入排序：',num2str(nA)]);
插入排序函數：InsertSort.m

function A = InsertSort(A)
% 感謝關註：matlab愛好者
% 插入排序演算法源代碼
% 作者：matlab愛好者

len = length(A);
for w = 1:len-1
% 從餘下序列中取出一個元素插入到新序列中
for v = w+1:-1:2
if(A(v)<A(v-1))
% 如果新元素小於所插入位置的元素，則交換
tmp = A(v-1);
A(v-1) = A(v);
A(v) = tmp;
else
% 否則保持位置不變
break;
end
end
end

『貳』 簡單而又生動的說明一下插入排序的原理，最好舉個例子！

就像摸牌。比如你手中有兩張比好大小的牌，小的放在左邊，大的放在右邊，你繼續摸牌，將摸到的牌的大小與手中兩張牌比較並放入這兩張牌的左邊，中間或右邊。繼續摸排，比較，插入，直至最後一張牌。這樣，就完成了插入排序。演算法中亦如此。希望能幫到你。

『叄』 VB插入排序演算法

Option Explicit

Private Sub Form_Load()
Dim i As Integer, intC As Integer
Dim IntOuSus() As String, strOuSus As String
Dim IntJiSus() As String, strJiSus As String

Randomize
For i = 1 To 30
intC = CInt(Rnd * 90) + 10
If intC Mod 2 = 1 Then
strJiSus = strJiSus & IIf(strJiSus = "", "", ",") & intC
Else
strOuSus = strOuSus & IIf(strOuSus = "", "", ",") & intC
End If
Next
IntOuSus = Split(strOuSus, ",")
IntJiSus = Split(strJiSus, ",")

OrderNumbers IntJiSus, "ASC"
OrderNumbers IntOuSus, "DESC"

End Sub

'注意以下過程中第一個參數使用了ByRef
'此方法比傳統的冒泡法快得多
Private Sub OrderNumbers(ByRef a() As String, Optional ByVal ASCDESC As String = "ASC")
Dim min As Long, max As Long, num As Long, first As Long, last As Long, temp As Long, all As New Collection, steps As Long
ASCDESC = UCase(ASCDESC)
min = LBound(a)
max = UBound(a)
all.Add a(min)
steps = 1
For num = min + 1 To max
last = all.Count
If a(num) < CDbl(all(1)) Then all.Add a(num), BEFORE:=1: GoTo nextnum '加到第一項
If a(num) > CDbl(all(last)) Then all.Add a(num), AFTER:=last: GoTo nextnum '加到最後一項

first = 1
Do While last > first + 1 '利用DO循環減少循環次數
temp = (last + first) \ 2
If a(num) > CDbl(all(temp)) Then
first = temp
Else
last = temp
steps = steps + 1
End If
Loop
all.Add a(num), BEFORE:=last '加到指定的索引

nextnum:
steps = steps + 1
Next
For num = min To max
If ASCDESC = "ASC" Then a(num) = CDbl(all(num - min + 1)): steps = steps + 1 '升序
If ASCDESC = "DESC" Then a(num) = CDbl(all(max - num + 1)): steps = steps + 1 '降序
Next
'MsgBox "本數組共經過 " & steps & "步實現" & IIf(ASCDESC = "ASC", "升序", "降序") & "排序！", 64, "INFORMATION"
Set all = Nothing
End Sub

『肆』 如何理解插入排序演算法

插入排序，如果你看的是數據結構書上的例子的話，他上邊說的有個什麼標志位，不用管這個，他的意思是，拿到一組數據，不先不要管是否是有序的。舉個列子。。如果現在你的 I 已經在第二個數上了，那麼就拿著這個數跟前邊的比較，如果小，把前邊那個數賦給當前位置，並且把當前數保存。接著就是邊往後移位邊比較，直到到第一個或者前面的比這個數小，停止，把這個數放在當前的位置，就OK了

『伍』 c語言插入法排序的演算法步驟

演算法描述
一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：
從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重復步驟2~5
如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。
范常式式碼
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;

while((j>=first) && (array[j] > temp))
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}

『陸』 誰能幫我具體分析下插入排序、冒泡排序、選擇排序三種方法的優劣著重分析三種排序所耗費的時間，穩定性

排序方法 最壞時間復雜度 最好時間復雜度 平均時間復雜度 穩定性
直接插入 O(n2) O(n) O(n2) 穩定
簡單選擇 O(n2) O(n2) O(n2) 不穩定
起泡排序 O(n2) O(n) O(n2) 穩定
快速排序 O(n2) O(nlog2n) O(nlog2n) 不穩定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) 不穩定
歸並排序 O(nlog2n) O(nlog2n) O(nlog2n) 穩定

『柒』 插入排序的原理

將n個元素的數列分為已有序和無序兩個部分，如下所示：
{{a1}，{a2，a3，a4，…，an}}
{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
…
{{a1(n-1），a2(n-1) ，…},{an(n-1)}}
每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。
假設在一個無序的數組中，要將該數組中的數按插入排序的方法從小到大排序。假設啊a[]={3,5,2,1,4};插入排序的思想就是比大小，滿足條件交換位置，一開始會像冒泡排序一樣，但會比冒泡多一步就是交換後（a[i]=a[i+1]後）原位置（a[i]）會繼續和前面的數比較滿足條件交換，直到a[i+1]前面的數組是有序的。比如在第二次比較後數組變成a[]={2,3,5,1,4};

『捌』 插入排序演算法

插入排序的基本思想是:每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序，這個時候就要用到一種新的排序方法--插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入演算法把要排序的數組分成兩部分:第一部分包含了這個數組的所有元素，但將最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

『玖』 插入排序的遞歸演算法

插入排序演算法：
C版本的分析如下：
//直接插入排序：從小到大排；
//演算法說明：
比如說現在排序進行到第
i位了，那麼1
到
i-1位都已經為有序序列了；然後將
r[0]和r[j]依次比較，若是r[j]>r[0],那麼就依次用前邊數據覆蓋後邊數據，不必擔心r[i]會丟掉，因為它被保存在了r[0]中，直到找到滿足r[i]<r[j]的位置,將r[0]數據寫入r[j]處，一次循環結束，進入下次循環；
void
insSort(
int
r[],int
length)
//傳數組，和數組大小；
{
//
數組下標從1
開始，
0號位為監視哨；
int
i=0,j=0;
for(i=2;i<=length;++i)
{
r[0]=r[i];
//總是用r[0]記錄當前數據；
j=i-1;
while(r[0]<r[j])
//尋找合適的位置；
{
r[j+1]=r[j];
//依次迭代覆蓋；
j=j-1;
}
r[j+1]=r[0];
//暈，終於找到滿足條件的地方了，趕緊鑽入；
}
}
大功告成！
希望能幫上你。。。

『拾』 插入排序

呃，先聲明下，這是我查課本後一個字一個字碼上去的，可不是ctrl+c,ctrl+v上去的···

插入排序有好幾種，如：直接插入排序，二分插入排序，表插入排序···
這里只介紹直接插入排序，其餘還望樓主自己上網找資料。
代碼(只給出整型數組排序）
void InsertSort(int*array,int n)
{
int i,j,t;//i表示插入次數，共進行n-1次插入
for(i=1;i<n;i++)
{
t=array[i];//把待排元素賦給t，移動
j=i-1;
while((j>=0)&&(t<array[j]))
{
array[j+1]=array[j];
j--;//順序比較和移動

}
array[j+1]=t;//再次移動
}
}

效率分析：
從空間上看：它只需要一個元素的輔助空間，用於元素的位置交換。
從時間分析：向有序表中逐個插入記錄的操作，進行了n-1次，每次操作分為比較關鍵碼和移動記錄，而比較次數和移動記錄的次數取決於待排序列關鍵碼的初始排列。
最好情況下，即待排序列已按關鍵碼有序，每次操作只需1次比較，2次移動。
總比較次數=n-1次
總移動次數=2(n-1)次
最壞情況下，即第j次操作，插入記錄需要同前面的j個記錄進行j次關鍵碼比較，移動記錄的次數為j+2次。
總比較次數=
n-1
∑j=(1/2)n(n-1);
j=1

總移動次數=
n-1
∑(j+1)=(1/2)n(n-1)+2n;
j=1

平均情況下，即第j次操作，插入記錄大約同前面的j/2個記錄進行關鍵碼比較，移動記錄次數為j/2+2次。

因此，直接插入排序的時間復雜度為O（n2)。
直接插入演算法的元素移動是順序的，該方法是穩定的。

希望能幫到你~~~