負數(shù)移到正數(shù)前面

已知順序表$(a_1,\dots ,a_n)$，每個元素都是整數(shù)，把所有值為負數(shù)的元素移到全部正數(shù)值元素前邊

算法思想

快排的前后指針版本
排序|冒泡排序|快速排序|霍爾版本|挖坑版本|前后指針版本|非遞歸版本|優(yōu)化|三數(shù)取中?-CSDN博客
前后兩個指針往后走
cur找負數(shù)，++prev，交換prev和cur的值
prev有兩種情況：

1. 在cur還沒遇到正數(shù)的時候，prev緊跟著cur
2. 在cur遇到正數(shù)的時候，prev在一組正數(shù)的前面
   交換：把正數(shù)往后推，把負數(shù)往前甩
   本質(zhì)是把一段正數(shù)的區(qū)間，推箱子似的往右推，同時把負數(shù)甩到左邊去

int Rearrange(SqList a, int n)
{int prev = 0;  //指針 prev，用于記錄負數(shù)區(qū)間的最后一個負數(shù)int cur = 0;   //指針 cur，用于遍歷數(shù)組中的每個元素while (cur < n)  //繼續(xù)遍歷直到 cur 超出數(shù)組范圍{if (a[cur] < 0)   //如果當前元素為負數(shù){Swap(&a[prev++], &a[cur]);  //將負數(shù)放到負數(shù)區(qū)間的末尾}++cur;            //移動 cur 到下一個元素}return prev;          //返回負數(shù)區(qū)間的結(jié)束位置
}

cur指向的是負數(shù)，與prev交換，prev++

cur++，判斷下一個元素

為3，cur繼續(xù)往下遍歷

cur指向-4，與prev交換，prev++

cur++

指向-1，與prev交換，prev++

cur++

為6，結(jié)束循環(huán)

小于x移到大于x前面

設有一元素為正數(shù)的線性表L(a1,a2,…,an)，存放在一維數(shù)組A[N]中，以an作為參考元素，將該表分為左右兩部分，左半部分的每個元素小于等于an，右半部分每個元素都大于an，an位于分界位置上，并把結(jié)果仍存放在A[N]中

int Rearrange(int a[], int n)
{int prev = 0;         //指針 prev，用于記錄小于an區(qū)間的最后一個負數(shù)int cur = 0;   //指針 cur，用于遍歷數(shù)組中的每個元素int keyi = n - 1;while (cur < n)  //繼續(xù)遍歷直到 cur 超出數(shù)組范圍{if (a[cur] < a[keyi])   //如果當前元素小于an{Swap(&a[prev++], &a[cur]);  //將其放到前半部分區(qū)間的末尾}++cur;            //移動 cur 到下一個元素}//只有在 prev 不等于 keyi 時才交換if (prev < keyi){Swap(&a[prev], &a[keyi]);}return prev;          //返回小于an的元素數(shù)量
}

奇數(shù)移到偶數(shù)前面

已知線性表按順序存儲，且每個元素都是整數(shù)均不相同，把所有奇數(shù)移到所有偶數(shù)前邊

思想同上

int Rearrange(SqList a, int n)
{int prev = 0;  //指針 prev，用于記錄負數(shù)區(qū)間的最后一個負數(shù)int cur = 0;   //指針 cur，用于遍歷數(shù)組中的每個元素while (cur < n)  //繼續(xù)遍歷直到 cur 超出數(shù)組范圍{if (a[cur] % 2 != 0)   //如果當前元素為奇數(shù){Swap(&a[prev++], &a[cur]);  //將奇數(shù)放到前半?yún)^(qū)間的末尾}++cur;            //移動 cur 到下一個元素}return prev;          //返回奇數(shù)區(qū)間的結(jié)束位置
}