[題目分析]本題屬於排序問題只是排出正負不排出大小可在數組首尾設兩個指針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
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23021.html
