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

admin2019-08-15 40

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

选项

答案采用类似于快速排序中的划分思想。算法如下： 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

学硕统考专业

清政府在鸦片战争中战败的主要原因是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

卡诺莎事件

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

TCP使用()机制来进行流量控制。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；

以下关于CPU的叙述中，错误的是()。

测量控制系统中的数据采集任务把所采集的数据送一个单缓冲区，计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。

设向量，如果，那么()．

机床包括（）等。

根据《文物保护法》的规定，迁移或者拆除()的，批准前须征得国务院文物行政部门同意。

为适应新形势的挑战，在积极扩大出口的同时，党中央确立了“走出去”的开放战略，鼓励有优势、有实力的企业走出去投资办厂，学习外国的先进经验，在经济全球化挑战的浪潮中，增强自身的竞争力。这是()。

【禹贡学会】

(2015年单选11)空姐甲长期在国外购买化妆品，经无申报通道携带入境，交由其表妹在网店销售，偷逃高额海关关税，获利数额巨大。甲的行为应认定为()。

计算其中Ω是圆柱面x2+y2－2x=0，平面z=0，z=a(a＞0)在第一卦限的区域．

Asthepaceoflifecontinuestoincrease,wearefastlosingtheartofrelaxation.Onceyouareinthehabitofrushingthroug