．[題目分析]題目要求重排n個元素且以順序存儲結構存儲的線性表使得所有值為負數的元素移到正數元素的前面這可采用快速排序的思想來實現只是提出暫存的第一個元素(樞軸)並不作為以後的比較標准比較的標准是元素是否為負數
int Rearrange(SeqList a; int n)∥a是具有n個元素的線性表以順序存儲結構存儲線性表的元素是整數本算法重排線性表a使所有值為負數的元素移到所有值為正數的數的前面
{i=; j=n;∥ ij為工作指針(下標)初始指向線性表a的第個和第n個元素
t=a[];∥暫存樞軸元素
while(i<j)
{while(i<j && a[j]>=) j;∥ 若當前元素為大於等於零則指針前移
if(i<j){a[i]=a[j];i++;}∥ 將負數前移
while(i<j &&a[i]<)i++;∥ 當前元素為負數時指針後移
if(i<j) a[j]=a[i];∥ 正數後移
}
a[i]=t;∥將原第一元素放到最終位置
}
[算法討論] 本算法時間復雜度為O(n)算法只是按題目要求把正負數分開如要求統計負數和大於等於零的個數則最後以t來定如t為負數則至i共i+個負數ni個正數(包括零)另外題目並未提及零的問題筆者將零放到正數一邊對此問題的擴充是若元素包含正數負數和零並要求按負數零正數的順序重排線性表統計負數零正數的個數請讀者利用上面解題思想自行解答
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23348.html
