问答题
设有一个数组中存放了一个无序的关键序列K
1
、K
2
、…、K
n
。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。【南京航空航天大学1997年】
【正确答案】
正确答案：算法的基本设计思想：以K。为枢轴进行一趟快速排序。将快速排序算法改为以最后一个为枢轴先从前向后再从后向前。算法的代码： int Partition(RecType K[]，int n)( ／／交换记录序列K[1．．n]中的记录，使枢轴记录到位，并返回其所在位置 ／／此时，在它之前的记录均不大于它 int i=1; j=n； K[o]=K[j]； DataType X=K[j]．key； while(i
=x) j一一； if(i
【答案解析】
提交答案
关闭