Question

C语言插入排序法

#include <stdio.h>
main()
{ int a[4],i,j,t;
printf("Please input 4 numbers: ");
for(i=0;i<4;i++)
scanf("%d",&a[i]);
for(i=1;i<4;i++)
{ t=a[i];
for( j=i-1 ; j>=0 && t>a[j] ; j-- )
a[j+1]=a[j];
a[j+1]=t;
}
printf("The sorted numbers: ");
for(i=0;i<4;i++)
printf("%d ",a[i]);
printf("\n"); }
我想不通的是这两句：
a[j+1]=a[j];
a[j+1]=t;
a[j+1]=t;这一句为什么要放在for循环里面,求教

Answer 1

for(i=1;i<4;i++) //外层
{
t=a[i];
for( j=i-1 ; j>=0 && t>a[j] ; j-- ) //内层
a[j+1]=a[j];
a[j+1]=t;
}
你要理解插入排序的原理，外层for从第二个数开始遍历（i从1开始），用t（即对应的a[i]）和其前面的所有值进行比较，如果t大，则该数后移一位，直到t小或者j小于0的时候退出内层for循环，这时候出现的格局就是所有在i位置之前比a[i]小的值全部后移了一位，退出循环时就会空出一个位置来。举个例子：输入：1 3 2 4
第一次循环时，t=a[1]=3，t>a[0]，所以a[0]后移一位（即：a[j+1]=a[j] -> a[1]=a[0]），之后出现结果：1124，这时候实际上0位置是给此时的t预留的位置，内层for执行完毕后，执行：a[j+1]=t 正好弥补这个空缺。结果：3124
第二次循环时，j=1，t=a[2]=2，t>a[1]，所以a[1]后移一位：a[2]=a[1]，之后结果：3114，在比较t和a[0]，t小，跳出内层for，跳出时j为0，执行：a[1]=t=2，结果：3214

下面就不讲了，从上面可以看出，你说的那一句，至关重要，外层for每循环一次就插入一位数据，而a[j+1]=t，就是完成插入的最后一步。。

追问

意思我是懂的，a[j+1]=t这一句直接写在a[j+1]=a[j]后面感觉就也像是for( j=i-1 ; j>=0 && t>a[j] ; j-- )的一个循环体啊。。

应该是这样理解把？我就纳闷a[j+1]=t为什么要在j--后面。。

追答

不是这样的，a[j+1]=t是在内层for循环的外面，执行的位置是当内层for判断条件不成立时。

追问

额懂啦。你画的图里面i++是不是应该在i-4的上一层啊

追答

哦，对的，应该是先i++，再判断i<4。你点击图片看，这么小看不清楚，那个是：i<4，就是外层for循环，条件成立（即Y），继续循环（i++），条件不成立就退出外层for循环（go on）

Answer 2

插入排序(insertion 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次后排序完毕

Answer 3

1. for( j=i-1 ; j>=0 && t>a[j] ; j-- )
a[j+1]=a[j];
表示将数组中插入位置开始的数向后移动。
2. a[j+1]=t;是为了将值插入到需要插入的位置上，共有四个数因此需要在循环体
for(i=1;i<4;i++)中循环执行三次
3. for( j=i-1 ; j>=0 && t>a[j] ; j-- )的循环体只有a[j+1]=a[j];
a[j+1]=t; 不是for( j=i-1 ; j>=0 && t>a[j] ; j-- )的循环体。

Answer 4

关键字比大小，大的作为左子女，否则作为右子女，如此递归，就站好队了。