2. 考研
  3. 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

admin2019-08-15  31
问题 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。
选项
答案 采用类似于快速排序中的划分思想。算法如下： void part(KeyType A[]，int n){ int i=1；j=n； KeyType temp； while(i＜j){ while(i＜j&&A[j]＞=0)j一一； ／／从右向左找负数 while(i＜j&&A[i]＜0)i++； ／／从左向右找非负数 if(i＜j){ ／／交换元素A[i]和A[j] temp=A[i]；A[i]=A[j]；A[j]=temp； i++；j一一： } } } 该算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/9KCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)