9.5　指针的应用（二）

指针可以方便地用来操作数组。

例题：写一程序，通过函数对一个int类型元素组成的数组按照插入法进行排序，然后输出。

插入法排序的基本思想是，把数据一个个地插入到一个有序的数组中。具体的实现可以用下面描述的方法进行。

首先数组被分为两个部分，已经排好序的部分和待插入的部分。显然只有一个元素时数组是有序的，所以一开始有序部分有一个元素，数组中其他部分都属于待插入部分。

例如，对于“int a[]={8,9,7,6,5,4,3,2,1,0}；”这个数组，最初有序部分和待插入部分分别为“{8}”和“{9,7,6,5,4,3,2,1,0}”。

然后每次从待插入部分拿出第一个插入到前面已经排好序的部分，这样排好序的部分就增加了一个元素，而待插入部分则减少了一个元素。最后当待插入部分没有任何元素时（dcr_tou < dcr_wei），则排序结束。这部分的功能由crpx()函数完成。

对于前面提到的数组来说，第一次插入意味着取出“9”插入到“{8}”这个数组中适当的位置。第二次意味着把“7”插入到“{8,9}”这个数组中……

把一个值（有序部分最后一个元素之后的元素即待插入部分的第一个元素）插入到一个有序数组中的解决过程是：首先把这个值与有序部分最后一个值进行比较，如果这个值大于等于有序部分最后一个值，则这个值的位置不动，插入结束。

以前面的数组为例，取出“9”的值与“8”比较，由于9大于8，所以“9”应该在“8”的后面不动，插入结束。有序部分变为“{8,9}”，待插入部分变为“{7,6,5,4,3,2,1,0}”。下一步取出“7”与前面的“9”比较。

如果这个值小于有序部分最后一个元素，则把有序部分最后一个元素向后移动一个位置，这样成了少了一个元素有序部分的同样的问题，所以可以通过递归解决。这个部分由cr()函数解决。

也就是说，由于7小于9，所以“9”移动到后面一个位置（“7”原来所在的位置）。这时，问题就变成了将“7”插入到“｛8｝”这个数组中合适位置的问题。显然这可以通过递归解决（“cr（yx_tou，yx_wei－1，crz）；”）。

程序代码9-20

输出结果如图9-15所示。

图9-15　指针的应用

在cr()函数中需要注意的是，其中的指针的最小值只能等于“a”，如果出现了小于“a”的情况，是一种未定义行为，这一点在写代码时需要特别小心。指向数组元素的指针可以在数组所在的内存段上移动（最多到指向数组最后元素之后的第一个同类型对象），但不可以超过这个范围。可见，对于指针同样存在着“越界”的问题。指向数组元素的指针可以通过加减法指向数组内部元素，或者数组后面第一个数据对象，超过这个范围则属于越界。当然，引用数组元素依然只能引用数组内部的。

练习

用选择法对一个一维数组排序。