问答题
已知线性表(a
1
，a
2
，a
3
，…，a
n
)存放在一维数组A中。试设计一个在时间和空间两方面都尽可能高效的算法，将所有奇数号元素移到所有偶数号元素前，并且不得改变奇数号(或偶数号)元素之间的相对顺序，要求：
问答题
给出算法的基本设计思想。
【正确答案】
【答案解析】算法的基本设计思想：
①在数组尾部从后往前，找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素“块”。
②暂存①中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。
③暂存②中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。
④如此继续，直到前一步的“块”前没有元素为止。
问答题
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
【正确答案】
【答案解析】算法的设计如下：
void Bubble_Swap(ElemType A[], int n){
int i=n, v=1; //i为工作指针，初始假设n为奇数，v为“块”的大小
ElemTvpe temp; //辅助变量
if(n%2==0) i=n-1; //若n为偶数，则令i为n-1
while(i＞1){ //假设数组从1开始存放。当i=1时，气泡浮出水面
temp=A[i-1]; //将“块”前的偶数号元素暂存
for(int j=0; j＜v; j++)//将大小为v的“块”整体向前平移
A[i-i+j]=A[i+j] //从前往后依次向前平移
A[i+v-1]=temp; //暂存的奇数号元素复制到平移后空出的位置
i=i-2; v++; //指针向前，块大小增1
} //while
}
问答题
说明你所设计算法的时间复杂度和空间复杂度。
【正确答案】
【答案解析】一共进行了n/2次交换，每次交换的元素个数从1～n/2，因此时间复杂度为O(n
2
)。虽然时间复杂度为O(n
2
)，但因n
2
前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1)。