沖刺必會代碼100題
順序表
1、已知線性表（a1,a2,…,an）按順序結構存儲且每個元素為不相等的整數。設計把所
有奇數移動到所有偶數前邊的算法（要求時間最少，輔助空間最少）。
【算法思想】：對于順序表L，從左向右找到偶數L.data[i]，從右向左找到奇數
L.data[j]，將兩者交換。循環這個過程直到i 大于j 為止。對應的算法如下：
void move(SqList &L)
{
int i = 0, j = L.length-1, k;
ElemType temp;
while(i <= j)
{
while(L.data[i]%2 == 1)
i++; //i 指向一個偶數
while(L.data[j]%2 == 0)
j--; //j 指向一個偶數
if(i < j)
{
temp = L.data[i]; //交換L.data[i]和L.data[j]
L.data[i] = L.data[j];
L.data[j] = temp;
}
}
}
本算法的時間復雜度為O(n)，空間復雜度為O(1)。
2、設計一個高效算法，將順序表L 中所有元素逆置，要求算法的空間復雜度為O(1)。
【算法思想】：掃描順序表L 的前半部分元素，對于元素L.datai,將其與后半部分對
應元素L.data[L. length-i-1]進行交換。對應的算法如下:
void reverse(