问题
问答题
已知数组A[1..n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
说明你所设计算法的时间复杂度和空间复杂度。
答案
参考答案：算法的时间复杂度为O(n)；算法的空间复杂度为O(1)。
解析： 本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组末端查找负整数，找到后进行交换，直到上、下界相遇。
具体做法是：设置两个指示器i和j，其中i=1，j=n；当A[i]为正整数，A[j]为负整数时，A[i]和A[j]交换；否则，A[i]为负整数时，则i++；A[j]为正整数时，则j-。这样，可使算法的时间复杂度为O(n)。