数据结构的试题

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145原序列有十个数: 10 18 4 3 6 12 1 9 18 8 [ 以10为基准,处理全部十个数 ] 10与8 互换,得到: 8 18 4 3 6 12 1 9 18 10 10与18互换,得到: 8 10 4 3 6 12 1 9 18 18 10与9 互换,得到: 8 9 4 3 6 12 1 10 18 18 10与12互换,得到: 8 9 4 3 6 10 1 12 18 18 10与1 互换,得到: 8 9 4 3 6 1 10 12 18 18 第1趟排序的结果: 8 9 4 3 6 1 10 12 18 18 [ 以8为基准,处理 8 9 4 3 6 1 ] 8与1互换,得到: 1 9 4 3 6 8 10 12 18 18 8与9互换,得到: 1 8 4 3 6 9 10 12 18 18 8与6互换,得到: 1 6 4 3 8 9 10 12 18 18 第2趟排序的结果: 1 6 4 3 8 9 10 12 18 18 [ 以1为基准,处理 1 6 4 3 ] 1比右边的数字都小,不用交换 第3趟排序的结果: 1 6 4 3 8 9 10 12 18 18 [ 以6为基准,处理 6 4 3 ] 6与3互换,得到: 1 3 4 6 8 9 10 12 18 18 第4趟排序的结果: 1 3 4 6 8 9 10 12 18 18 [ 以3为基准,处理 3 4 ] 3比4小,不用交换 第5趟排序的结果: 1 3 4 6 8 9 10 12 18 18 [ 以12为基准,处理 12 18 18 ] 12比右边的数字都小,不用交换 第6趟排序的结果: 1 3 4 6 8 9 10 12 18 18 [ 以18为基准,处理 18 18 ] 18与18不用交换 第7趟排序的结果: 1 3 4 6 8 9 10 12 18 18 这就是最后的排序结果. // C语言测试程序 #include #define MAXSIZE 10000 /* 用于要排序数组个数最大值，可根据需要修改 */ typedef struct{ int r[MAXSIZE+1];
/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */ int length;
/* 用于记录顺序表的长度 */}SqList; int g_count; /* 交换L中数组r的下标为i和j的值 */void swapData(SqList *L,int i,int j){ int temp=L->r[i]; L->r[i]=L->r[j]; L->r[j]=temp;} void printData(SqList L){ int i; printf("(%d) ",g_count); for(i=1;ir[low]; /* 用子表的第一个记录作枢轴记录 */ while(lowr[high]>=pivotkey) high--; swapData(L,low,high);/* 将比枢轴记录小的记录交换到低端 */ while(lowr[low]<=pivotkey) low++; swapData(L,low,high);/* 将比枢轴记录大的记录交换到高端 */ } return low; /* 返回枢轴所在位置 */} /* 对顺序表L中的子序列L->r[low..high]作快速排序 */void QSort(SqList *L,int low,int high){ int pivot; if(lowr[low..high]一分为二，算出枢轴值pivot */ ////////测试 printData(*L); //////// QSort(L,low,pivot-1);
/* 对低子表递归排序 */ QSort(L,pivot+1,high);
/* 对高子表递归排序 */ }} /* 对顺序表L作快速排序 */void QuickSort(SqList *L){ QSort(L,1,L->length);} int main(){ int d[]={10,18,4,3,6,12,1,9,18,8}; int N; int i; SqList LT; N=sizeof(d)/sizeof(int); for(i=0;i