问题描述：用指针实现一个给定数组的数组元素的插入法排序
解题思路：
1.为了提高数组元素的输入效率，采用从文件中读取数据，使用freopn()函数。
2.将数组元素分成有序sequence和无序disorder两个部分，设置两个指针sequen_head 和sequen_rear分别指向有序部分的第一个和最后一个元素，再设置两个指针disorder_head和disorder_rear分别指向无序部分的第一个元素和最后一个元素的后面一个位置。
初始时，有序部分只有一个元素（即数组的第一个元素），sequen_head 和sequen_rear都指向该元素；disorder_head指针指向数组的第二个元素；每次从无序的部分拿出第一个元素插入到有序部分，直到无序集为空集，即disorder_head不小于disorder_rear 。
3.插入过程：将待插入元素 disorder_head与有序部分最后一个元素 sequen_rear进行比较，若大于则插入过程结束；若被比较元素sequen_rear是第一个元素，交换两个元素位置，插入结束；否则，将有序集的最后一个元素sequen_rear后移一个位置，然后递归地将待插入元素*disorder_head插入到除最后一个元素之外的有序集。
4.输出排好序的数组元素。
从以上分析过程可以将整个实现过程用四个函数实现，分别是初始化函数initialize()、选择插入元素函数sort()、插入函数insert()和输出函数output()。freopen()函数被初始化函数所调用。
完整代码：
/*问题:给定一个数组,对其数组元素采用插入法进行排序
Written by: Jimmy Tung
Date : 2020.04.08
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //数组元素个数
void initialize( int * , int * ); //初始化数组
void sort( int * , int * ); //排序
void insert( int *, int * , const int ); //将选择的元素插入有序部分
void output( int *, int *); //输出排序结果
int main(void)
{
int array[MAXSIZE]; //命名数组
//初始化数组
initialize( array , *(&array + 1) );
//排序
sort( array , *(&array + 1) );
//输出
output( array , *(&array + 1) );
system("PAUSE");
return 0;
}
//初始化数组{8 9 7 6 5 4 3 2 1 0}
void initialize( int *head , int *rear)
{
freopen("E:\\测试数据.txt", "r", stdin);
while( head < rear )
{
scanf("%d", head++);
}
freopen("CON", "r", stdin);
}
//排序：将数组分为有序sequence和无序disorder两部分
void sort( int *head , int *rear )
{
int *sequen_head = head, *sequen_rear = head;
int *disorder_head = head + 1, *disorder_rear = rear;
while( disorder_head < disorder_rear )
{
insert( sequen_head, sequen_rear , *disorder_head);
sequen_rear++;
disorder_head++;
}
}
//递归地将值插入到有序部分
void insert( int *head, int *rear , const int value)
{
if( value >= *(rear)) //递归终止条件
{
return;
}
*(rear + 1) = *rear; //向后移动元素
if( head == rear) //递归终止条件
{
*head = value;
}
else
insert( head, rear -1 , value); //递归过程
}
//输出排序结果
void output( int *head, int *rear)
{
printf("数组排序结果为:");
while( head < rear)
{
printf("%d,", *head++);
}
putchar('\n');
}
结果如下：
输入：8, 9, 7, 6, 5, 4, 3, 2, 1, 0
输出：0,1,2,3,4,5,6,7,8,9,
请按任意键继续. . .
Process returned 0 (0x0) execution time : 6.871 s
Press any key to continue.
要点复盘：
1.sort()函数的参数分析
形参类型都是 int *类型，实参如下。
sort( array , *(&array + 1) );
sort()函数的第一个实参是数组名array，我们知道数组名是一个指向数组起始元素的指针，所以此处的array是一个 int类型的指针，其左值是指向一个大小为sizeof(int)的内存区域，即数组起始元素所占的内存区域，array的值（右值）是该内存区域的第一个内存单元的编号。 array的右值在sort()函数的函数体执行前将会被赋给形参head。
&是求指针运算符，运算对象为左值表达式，所以运算结果&array是指向array数组的一个指针常量，数据类型为 int ( * ) [MAXSIZE]。指针常量&array指向的内存区域大小为sizeof(int)MAXSIZE。&array + 1 指向下一个类型为 int ( * ) [MAXSIZE]，大小和array数组一样大的内存区域。
“ * ”是间接引用运算符，运算对象为指针，运算结果为指针所指向的那块内存或者那块内存中数据的值。所以(&array + 1) 就是array数组后一个与array数组同类型和大小的内存区域。可以认为，(&array + 1)相当于这个数组的数组名，其右值为该数组起始元素第一个内存单元的编号（也是array数组后一个int类型内存区域的地址编号），该值在sort()函数的函数体执行前会被赋给形参rear。可以通过以下代码验证。
printf("%p %p\n", array + MAXSIZE - 1 , *(&array + 1));
printf("%d\n", sizeof *(&array + 1) );
2.insert()函数的分析
先看该函数的实参，首先需要明确一点，实参是右值表达式，将被赋给形参。
insert( sequen_head, sequen_rear , *disorder_head);
前两个参数定位了有序部分的区域，第三个参数*disorder_head在此处是右值的含义，是disorder_head指针所指向的数组元素的值。
再看函数体，两种情况停止递归，分别是当带插入元素值value不小于有序集最后一个元素值和有序集只有一个元素的时候，其余情况再次调用insert()函数完成插入操作。
问题思考：
1.算法上可做哪些优化？
（1）插入过程采用二分插入
2.是否可以减少指针的数量？
（1）有序部分头指针没有用到
