/**功能：排序*日期：2017年9月24日*作者：yzh*开发环境：QT**/#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_STACK_LENGTH100//非递归快速排序调用栈#defineMAX_LENGTH20//数组最大值//对于数值型keyType#defineEQ(a,b)((a)==(b))//比较a==b?#defineLT(a,b)((a)<(b))//比较a<b?#defineLQ(a,b)((a)<=(b))//比较a<=b?typedefintKeyType;//查找关键字类型typedefcharInfoType;//其他信息typedefstruct{//信息体KeyTypekey;InfoTypeotherInfo;}RedType;typedefstruct{//数组结构RedTyper[MAX_LENGTH+1];//r[0]闲置或用作哨兵；intlength;}SqList;typedefstruct{//栈节点intl,h;}StackNode;typedefstruct{//栈StackNodenode[MAX_STACK_LENGTH];intidx;}Stack;//插入模拟数据intinsertSQ(SqList*list){for(inti=1;i<MAX_LENGTH+1;i++){list->r[i].key=rand()%1000;list->r[i].otherInfo=96+i;}list->length=MAX_LENGTH+1;}//打印数组intprintf_SQ(SqList*list){for(inti=1;i<list->length;i++){if(i<list->length-1){printf("%d,",list->r[i]);}else{printf("%d\n",list->r[i]);}}}//插入排序intsort_I(SqList*list){inti,j;for(i=2;i<list->length;++i){if(LT(list->r[i].key,list->r[i-1].key)){list->r[0]=list->r[i];list->r[i]=list->r[i-1];for(j=i-2;LT(list->r[0].key,list->r[j].key);--j){list->r[j+1]=list->r[j];}list->r[j+1]=list->r[0];}}}//插入排序改进：折半插入排序intsort_B_I(SqList*l){inti,j;intlow,high,mid;for(i=2;i<l->length;i++){if(LT(l->r[i].key,l->r[i-1].key)){l->r[0]=l->r[i];l->r[i]=l->r[i-1];low=1;high=i-2;while(low<=high){mid=(low+high)/2;if(LT(l->r[0].key,l->r[mid].key)){high=mid-1;}else{low=mid+1;}}for(j=i-2;j>high;j--){l->r[j+1]=l->r[j];}l->r[high+1]=l->r[0];}}}//冒泡排序intsort_B(SqList*list){inti,j;for(i=1;i<list->length;i++){for(j=i+1;j<list->length;j++){if(LT(list->r[j].key,list->r[i].key)){list->r[0]=list->r[j];list->r[j]=list->r[i];list->r[i]=list->r[0];}}}}//选择排序intsort_S(SqList*list){inti,j;for(i=1;i<list->length;i++){list->r[0]=list->r[i];intmin=i;for(j=i+1;j<list->length;j++){if(LT(list->r[j].key,list->r[0].key)){list->r[0]=list->r[j];min=j;}}list->r[min]=list->r[i];list->r[i]=list->r[0];}}//快速排序intPartition(SqList*L,intl,inth){L->r[0]=L->r[l];while(LT(l,h)){while(LT(l,h)&&LT(L->r[0].key,L->r[h].key)){--h;}L->r[l]=L->r[h];while(LT(l,h)&&LQ(L->r[l].key,L->r[0].key)){++l;}L->r[h]=L->r[l];}L->r[l]=L->r[0];returnl;}//递归算法voidQSort(SqList*L,intlow,inthigh){//算法10.7//对顺序表L中的子序列L.r[low..high]进行快速排序intpivotloc;if(low<high){//长度大于1pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}//QSortStackNodepop(Stack*stack){StackNodenode=stack->node[stack->idx];stack->idx--;returnnode;}voidpush(Stack*stack,intl,inth){stack->idx++;stack->node[stack->idx].h=h;stack->node[stack->idx].l=l;}//非递归算法voidsort_Q(SqList*L,intlow,inthigh){intpivotloc;Stackstack;push(&stack,low,high);StackNodenode;while(stack.idx>0){node=pop(&stack);if(node.l<node.h){pivotloc=Partition(L,node.l,node.h);push(&stack,pivotloc+1,node.h);push(&stack,node.l,pivotloc-1);}}}voidQuickSort(SqList*L){//算法10.8//对顺序表L进行快速排序//sort_Q(L,1,L->length-1);//调用非递归快速排序//QSort(L,1,L->length-1);//调用递归快速排序}//QuickSortintmain(intargc,char*argv[]){//测试栈//Stackstack;//push(&stack,1,2);//push(&stack,2,3);//push(&stack,4,6);//StackNodenode=pop(&stack);//printf("%d,%d\n",node.l,node.h);//StackNodenode2=pop(&stack);//printf("%d,%d\n",node2.l,node2.h);//StackNodenode3=pop(&stack);//printf("%d,%d\n",node3.l,node3.h);//return0;SqListlist;insertSQ(&list);//插入模拟数据printf_SQ(&list);//打印测试数据//（41,467,334,500,169,724,478,358,962,464,705,145,281,827,961,491,995,942,827,436）printf("-------------------------------------------\n");//sort_B(&list);//冒泡排序//sort_I(&list);//插入排序//sort_S(&list);//选择排序//sort_B_I(&list);//插入排序改进：折中插入排序QuickSort(&list);//快速排序printf_SQ(&list);//打印排序后数组//(41,145,169,281,334,358,436,464,467,478,491,500,705,724,827,827,942,961,962,995)printf("-------------------------------------------\n");return0;}