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