试设计一个算法 使得在尽可能少的时间内重排数组 将所有取负值的排序码放在所有取非负值的排序码之前。

(1)数据结构
   typedef int KeyType;
   typedef int DataType;
   typedef struct{
     KeyType key;    /*排序码字段*/
     DataType info;    /*记录的其他字段*/
   }RecordNode;
   typedef struct{
     intn;    /*n为文件中的记录个数*/
     RecordNode*record;
   }SortObject;
   (2)思路
   采用类似快速排序的方法。设置两个下标变量i和j。i(初值为0)从前向后扫描，j(初值为n-1)从后向前扫描。每当record[i]＞=0且record[j]＜0时，将记录record[i]与recordS]交换。到i与j相等时，所有取负值的排序码已被放在所有取非负值的排序码之前，算法结束。
   (3)算法
   void SortInt(Sortobject*pvector){
     inti,j;
     RecordNode temp;
     i=0:
     j=pvector-＞n-1:
     while(i＜j){
       while(pvector-＞record[i].key＜0)i++;
       while(pvector-＞record[j].key＞=0)j--;
       if(i＜j){
         temp=pvector-＞record[i];
         pvector-＞record[i]=pvector-＞record[j];
         pvector-＞record[j]=temp;    /*交换记录*/
         i++;    /*i从前向后扫描*/
         j--;    /*j从后向前扫描*/
       }
     }
   }
   (4)时间代价分析
   本算法从形式上看是一个两重循环，但是，外层循环从i=0，j=n-1开始执行，循环条件是i＜j，每执行一次外层循环，i最少加1，j最少减1，两个内层循环每执行一次都将i++或者j--，所以内层循环执行次数总计不超过n，整个二重循环执行的时间代价为O(n)。