数据结构考研分类复习真题 第五章 答案[39]

[题目分析]本题属于排序问题只是排出正负不排出大小可在数组首尾设两个指针i和ji自小至大搜索到负数停止j自大至小搜索到正数停止然后i和j所指数据交换继续以上过程直到 i=j为止

void Arrange(int A[]int n)//n个整数存于数组A中本算法将数组中所有正数排在所有负数的前面

{int i=j=nx; //用类C编写数组下标从开始

while(i<j)

{while(i<j && A[i]>) i++;

while(i<j && A[j]<) j;

if(i<j) {x=A[i]; A[i++]=A[j]; A[j]=x; }//交换A[i] 与A[j]

}

} //算法Arrange结束

[算法讨论]对数组中元素各比较一次比较次数为n最佳情况(已排好正数在前负数在后)不发生交换最差情况(负数均在正数前面)发生n/次交换用类c编写数组界偶是n空间复杂度为O()

类似本题的其它题的解答:

（）与上面题同因要求空间复杂度也是O(n)可另设一数组C对A数组从左到右扫描小于零的数在C中从左（低下标）到右（高下标）存大于等于零的数在C中从右到左存

（）将题中判定正数(A[i]>)改为判偶数(A[i]%==)将判负数(A[j]<)改为(A[j]%!=)

（）同（）只是要求奇数排在偶数之前

（）利用快速排序思想进行一趟划分

int Partition(int A[]int n)//将n个元素的数组A调整为左右两部分且左边所有元素小于右边所有元素返回分界位置

{int i=j=nrp=A[]; //设数组元素为整型

while(i<j)

{while(i<j &&A[j]>=rp) j;

while(i<j &&A[i]<=rp) i++;

if(i<j) { x=A[i];A[i]=A[j]; A[j]=x; }

}

A[i]=rp; return(i); //分界元素

} // Partition

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []