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

admin2019-08-15 85

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

选项

答案采用类似于快速排序中的划分思想。算法如下： 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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

中国共产党在大革命失败后，根据中国革命的新特点，明确了“工农武装割据”的思想，其核心内容不包括()。

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

下列的网络协议中，()的运输层协议是使用TCP的。

为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，()不是一定需要。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

下列关于RISC的叙述中，错误的是()。

A、右房、右室大B、肺血减少，P2减弱C、两者均有D、两者均无室间隔缺损可见

早产低出生体重儿出现硬肿症，下列哪项治疗最重要

关于国家发射卫星的责任，依《外空条约》和《责任公约》的规定，下列说法正确的是哪项?()

(2008、2009年)工程建设监理单位的工作内容，下列哪条是正确的?()

下列火灾隐患中不属于当场改正并督促落实的是()。

某项贷款年利率为8％，银行要求的补偿性余额维持在25％水平基础上。那么该贷款的实际利率是()。

_________是斯特拉文斯基1913年创作的舞剧音乐，20世纪影响最大的作品之一，它描写了俄国古代未开化民族在春天祭祀大地的仪式。

求函数f(x)=xe2-x的单调区间、凹凸区间、极值及拐点．

有人认为：“如果事物的表现形式和事物的本质会直接合二为一，一些科学家就都成为多余的了。”这一命题

InWesternCulturesyoudon’topenacloseddoorwithoutknocking,unlessitisyourownoroneclearlyinapublicplace.Or【M1