【正确答案】(1)数据结构
   SortObject的定义。
   (2)思路
   设有n个记录需要排序。在最差情况下，每趟分区使得左区长度为0。这时，栈的最大深度为2n，平均时间代价是O(n)。栈最深时的状态如下所示：
   0，-1，1，0，2，1，3，2，…，n-2，n-3，n-1，n-1，…
   可以修改上述算法，使得每次分区后，较长的区的两个边界先进栈，较短的区的两个边界后进栈。修改后的算法如下所示(加粗的部分是与原算法不同的地方)。
   (3)算法
   void qsort1(SortObject*pvector,int ol,int or){/*非递归快速排序*/
       int 1,r, pivotindex,i,j;
       DataType temp;
       RecordNode pivot;
       PSeqStack pastack=createEmptyStack_seq();
       /*一个栈,用来存放每个区的两个边界*/
       temp.left=ol;
       temp.right=or;
       push_seq(pastack,temp);    /*两个边界进栈*/
       while(!isEmptyStack_seq(pastack)){    /*每当栈不空*/
           temp=top_seq(pastack);
           1=temp.left;
           r=temp.right;
           pop_seq(pastack);    /*取栈顶,出栈*/
           if(1＞=r){
               continue;
           }    /*只有一个记录或无记录,无需排序*/
           pivotindex=1;
           pivot=pvector-＞record[pivotindex];    /*取轴值*/
           i=1;
           j=r;
           while(i!=j){   /*寻找轴值的最终位置*/
               while((pVector-＞record[j].key＞=pivot.key)&&(j＞i))
                 j--;
           if(i＜j)
                 pvector-＞record[i++]=pvector-＞record[j];
           while((pVecto-＞record[i].key＜=pivot.key)&&(j＞i))
                 i++:
       if(i＜j)
           pvector-＞record[j--]=pvector-＞record[i];
       }
       pvector-＞record[i]=pivot;    /*找到轴值的最终位置*/
       if(r-i＜i-l){    /*右区长度r-i小于左区长度i-l*/
           temp.left=1:
           temp.right=i-1:
           push_seq(pastack,temp);    /*左区两个边界先进栈*/
           temp.left=i+1:
           temp.right=r:
           push_seq(pastack,temp);    /*右区两个边界后进栈*/
       }
       else {    /*右区长度r-i大于等于左区长度i-l*/
           temp.left=i+1:
           temp.right=r:
           push_seq(pastack,temp);    /*右区两个边界先进栈*/
           temp.left=l:
           temp.right=i-l:
           push_seq(pastack,temp);    /*左区两个边界后进栈*/
       }
     }
   }
   (4)代价分析
   对于修改后的算法，栈最深的情形是每次分区的左右两区长度相等或相差1。这时，栈的最大深度为2[log₂n+1)]，平均时间代价是O(log₂n)。其中，[n]表示不超过n的最大整数。与快速排序算法相同，该算法的平均时间复杂度为O(nlog₂n)。