插入排序的算法和分析

‘壹’ 插入排序的算法

排序算法在编程领域中起着举足轻重的作用，在目标检索、机器学习、数值计算、图像处理等领域有着广泛地应用。为了追本溯源，公众号特推出常用经典排序算法系列推文，让小伙伴们深入了解排序算法的实现原理，同时也提升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)。
直接插入算法的元素移动是顺序的，该方法是稳定的。

希望能帮到你~~~