发布时间 : 星期二 文章C语言典例解析更新完毕开始阅读
其基本思路是：首先在数组a[ ]中已经排好序的前k个元素（即a[0]、a[1]、a[2]、?a[k-1]）中找第k+1个元素a[k]的插入位置，然后将已经排好序的前k个元素中比a[k]大的a[k-1]、a[k-2] ?都右移一个位置，最后再将a[k]插入。这样，当k的取值从1至n-1时，并且对每一个k值都重复上面操作，就实现了对整型数组a[ ]中的n个元素从小到大排序。
在函数psort1（）中，找a数组中的第k个元素a[k]在已经排好序的前k个元素中的插入位置采用了二分法查找。在函数中分别采用变量low和high表示当前查找范围的下界和上界，变量i表示当前正在处理的元素在数组中的位置，变量k表示已经排好序的不同元素个数。每次进行二分法查找时，是在已经排好序的不同元素中查找元素a[i]的插入位置。因此，当前查找范围的下界low的值为0，当前查找范围的上界high的值为k-1。即（1）空的答案为k-1。在查找时，首先计算查找范围的中间位置：mid=（low+high）/2。然后用a[i]与a数组中mid位置的元素a[mid]比较，若a[i]的值大于a[mid]的值，则表示新的查找范围应为mid+1至high间。若a[i]的值小于等于a[mid]的值，则表示新的查找范围应为low至mid-1间。反复做上面语句，直到low>high时结束。查找结束后，a数组中low就是插入的位置。根据题意，若a[low]与当前待处理元素a[i]不相等，则需要插入，否则忽略该元素。同时还要考虑到边界问题，当元素a[i]的值大于前面所有已经排好序的元素时，low的值为k，此时a[low]的值可能与a[i]相等，但也需要插入。因此，当low==k或者a[i]!=a[low]时，需将a[i]插入。因此，（2）空的答案为a[i]!=a[low]。在插入前，需将已经排好序的元素中比a[i]大的a[k-1]、a[k-2]、......、a[low]都右移一个位置，最后再将a[i]插入。为了实现该功能，在函数中先将a[i]的值赋给变量t，然后通过（3）空和（4）空所在的循环语句实现比a[i]大的a[k-1]、a[k-2]、......、a[low]元素都右移一个位置。因此，循环变量j的初始值为k-1，循环的终止值为low，每次循环都将j减1。即（3）空的答案为k-1，（4）空的答案为low。执行完上面的循环后，已将待插入a[i]元素的位置low空出来，此时可将a[i]的值（循环前已经将a[i]的值赋给了t）插入到a数组中low的位置，即a[low]=t。因此，（5）空的答案为low。由于插入一个元素后，已经排好序的不同元素的个数增加了。因此，（6）空的答案为k++或者能使k增1的语句。
22.改进冒泡排序
函数void sort3（int a[ ], int n）是对数组a中的n个元素按从小到大顺序排序，排序方法采用了改进的冒泡排序方法。即在每趟排序中比较至上一趟最后一次交换的位置。 〔函数〕
sort3（int a[ ], int n） /* 数组a为存放待排数据的数组，n为a数组中元素的个数 */ { int k,j,m; int t;
___（1）___; while（m>0）
{ for（k=j=0;j
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; ___（2）___; }
m=___（3）___; /* 本空填m-1不给分 */ } } 答案：
（1）m=n-1 （2）k=j （3）k
分析：
在进行从小到大排序的冒泡排序中，每趟排序实现了将最大的元素安置到未排序部分的最后位置，即最终位置。由于在每趟排序过程中，通过相邻元素关键字两两比较，大的元素在不断的往下沉或往后靠，小的元素在不断往上冒或往前靠。每经过一趟排序，每个元素都向目标位置靠近一些，而且在每趟的最后交换的位置后的元素都已经按序排列。根据上面的思路，对n个元素进行第k（1<=k<=n-1）趟排序，首先需在第k-1（2<=k<=n-1）趟排序时记下最后交换的位置m，然后在第k（1<=k<=n-1）趟排序时，将第一个元素与第二个元素进行比较，符合交换条件时，进行交换。再比较第二个元素和第三个元素。依次类推，直至第m-1个元素和第m个元素进行比较，而不需要比较至第n-k-1个元素。由于在第一趟排序时，没有上一趟排序的m值。因此，还要设置m的初始值n-1。即（1）空的答案为m=n-1。为了记录每趟排序中最后一次交换的位置，在内循环中只要出现交换，就用某变量记录该交换的位置，这样，当内循环结束（即完成一趟排序）时，该变量中存放的就是最后一次交换的位置。因此，（2）空处的语句是记录每次交换的位置，即（2）空的答案为k=j。根据前面分析，下一趟排序的比较结束位置是当前这一趟排序的最后一次交换位置，因此，（3）空的答案为k。
23.冒泡排序
函数void sort2（int a[ ], int n）是对数组a中的n个元素按从小到大顺序排序，排序方法采用了改进的冒泡排序方法。即当某趟排序中，不出现交换就停止排序。 〔函数〕
void sort2（int a[ ], int n）
/* 数组a为存放待排数据的数组，n为a数组中元素的个数 */ { int i,j,k ; int t;
___（1）___;i=n-1; while（k） { k=0;
for（j=0;j
{ t=a[j];a[j]=a[j+1];a[j+1]=t;___（2）___;}
___（3）___; } } 答案：
（1）k=1或k=某一非0值 （2）k=1或k=某一非0值 （3）i－－
分析：
从冒泡排序的过程可以看出，如果在某一趟排序的过程中，不出现交换，则说明每两个元素进行比较时，都已不符合交换条件，即对升序排序来说，每对相邻的元素中的前一个元素都已比后一个元素小（a[j] 在函数sort2（）中，引入了标志变量k来表示每趟排序是否出现过交换。开始时，为了能使排序进行，应给k赋初始值1或其他非0值。因此，（1）空的答案为k=1或k=某一个非0值。进行每一趟排序前，函数中已经给k赋值为0，表示没有交换。当该趟排序中某两个元素不符合排序要求时，则将这两个元素进行交换，同时还需改变标志变量k为1或其他的非0值，表示在该趟排序中已经出现了交换。因此，（2）空的答案为k=1或k=某一个非0值。根据冒泡排序方法，第一趟排序时，需对前n个元素进行两两比较，即第一个元素与第二个元素比较、第二个元素与第三个元素比较、?、第n-1个元素与第n个元素比较。由于经过第一趟比较与交换后，已经使最大的元素存入了最后一个位置。因而在第二趟排序时，只需对前n-1个元素进行两两比较。在第三趟排序时，只需对前n-2个元素进行两两比较。每经过一趟排序，需参加比较的元素就少1。因此，（3）空的答案为i－－或能使i的值减1的等价语句。