插入排序

C语言的插入排序法是什么？

插入排序(inrtion sort)

如果需要对一个小型数组进行升序排列，那么可以选用插入排序，插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。

可以把左手中的牌比做已经摸起的牌，即已经被排列好的牌，左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同；而在桌子上的那部分没摸的牌则是未被排序的牌，这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分。

一开始摸起的第一张牌不需要排序，可以认定其为已排序的牌。

如果用外层循环for来表示摸起的牌的话，则可以抽象为：

// 对象数组

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 从数组的第二个元素开始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j记录已排序部分的最后一张牌的位置

. . .

}

而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置，这里示范的排列策略是升序排列，摸起了这张牌后，便自右向左地和手中的牌进行比较。

把pick称作摸起的牌，如果pick比手中的牌小，则手中较大的那张牌就向右挪一位，pick再和下一张牌做比较，如果下一张牌仍然比pick大，那么那张牌便也向右移动一个位置，依此类推。

如果手中下一张和pick比较的牌比pick小，那么pick就被插入在了手中前一张牌移动后空下的位置；

或者手中所有的牌都比pick大，那么所有的牌就都向右移动过一个位置，所以pick最终被插入在了手中最左边的位置。

这个过程可以抽象为：

// 对象数组

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 从数组的第二个元素开始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j记录已排序部分的最后一张牌的位置

// 如果循环了j+1次，即j = -1时还未找到比pick小的牌

// 那么pick就是最小的牌被插入在位置A[0]处

// A[j]是当前手中和pick进行比较的牌

while(j >= 0 && A[j] > pick)

{

// 未找到可插入位置，则A[j]向后挪一位

A[j+1] = A[j];

// j减1继续向左定位手中下一张供和pick比较的牌--j;

}


// while结束后，j+1所表达的位置便是pick可以插入的位置

A[j+1] = pick;

}

// 对于有N个元素的数组A，采用插入排序法排序时，当外层循环进行了N-1次后排序完毕

插入排序的分类

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。
例如,已知待排序的一组纪录是：
60,71,49,11,24,3,66
假设在排序过程中，前3个纪录已按关键码值递增的次序重新排列，构成一个有序序列：
49,60,71
将待排序纪录中的第4个纪录（即11）插入上述有序序列，以得到一个新的含4个纪录的有序序列。首先，应找到11的插入位置，再进行插入。可以讲11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的纪录依照同样的方法逐个插入到该有序序列中。若纪录数n,续进行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。
直接插入排序算法：
public void zjinrt (Redtype r[],int n)
{
int I,j;
Redtype temp;
for (i=1;i<n;i++)
{
temp = r[i];
j=i-1;
while (j>-1 &&temp.key<r[j].key)
{
r[j+1]=r[j];
j--;
}
r[j+1]=temp;
}
} 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。所谓折半比较，就是在插入A[i]时，取A[i-1/2]的关键码值与A[i]的关键码值进行比较，如果A[i]的关键码值小于A[i-1/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，故可以在A[0]到A[i-1/2-1]之间继续使用折半比较；否则只能插入A[i-1/2]到A[i-1]之间，故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半，其中间结点为A[k+r/2]，经过一次比较即可排除一半纪录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是文件纪录必须按顺序存储。
折半插入排序的算法思想：
算法的基本过程：
（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。
3 希尔排序法
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
各组内的排序通常采用直接插入法。由于开始时s的取值较大，每组内记录数较少，所以排序比较快。随着不断增大，每组内的记录数逐步增多，但由于已经按排好序，因此排序速度也比较快。

插入排序过程详解

从有序数列和无序数列{a2,a3，…，an}开始进行排序；处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，ai-2，…，a1进行比较，找出合适的位置将ai插入；重复第二步，共进行n-i次插入处理，数列全部有序。

注意事项：

折半插入排序是对直接插入排序的一种改良方式，在直接插入排序中，每次向已排序序列中插入元素时，都要去寻找插入元素的合适位置，但是这个过程是从已排序序列的最后开始逐一去比较大小的，这其实很是浪费，因为每比较一次紧接着就是元素的移动。

直接插入排序的介绍

在日常生活中，经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。例如：一组从小到大排好顺序的数据列{1,2,3,4,5,6,7,9,10}，通常称之为有序列，我们用序号1,2,3，…表示数据的位置，欲把一个新的数据8插入到上述序列中。完成这个工作的步骤：①确定数据“8”在原有序列中应该占有的位置序号。数据“8”所处的位置应满足小于或等于该位置右边所有的数据，大于其左边位置上所有的数据。②将这个位置空出来，将数据“8”插进去。直接插入排序(straight inrtion sort)的做法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

插入排序的设计步骤

算法设计有很多方法。插入排序使用的是增量（incremental）方法；在排好子数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；
步骤
⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；
⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。
思路
假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.