题目
有一个顺序表L，其元素为整型数据，设计一个算法，将L中所有小于表头元素的整数放在前半部分，大于表头元素的整数放在后半部分。
分析
遍历顺序表L中的所有元素，将其与表头元素比较，如果小于表头元素，则从该元素位置开始，将其之前的所有元素向后移动一个位置，并将该元素放入移动后的空位（也可以说是表头位置）。
核心代码：
/* 移动元素将L中所有小于表头元素的整数放在前半部分，大于表头元素的放在后半部分（注意：没有考虑与表头元素相等的元素） */
/* L[]指的是要移动的顺序表；m指的是顺序表中元素的个数 */
void moveEle(int L[],int m){
int k=0;// 记录表头元素的下标
int temp=L[k];// 记录表头元素的值
int i=0;// 记录循环
while(i<m){
if(L[i]<temp){// 判断是否小于表头元素
int save=L[i];// 保存小于表头的元素
for(int q=i;q>0;q--){// 将L[i]之前的所有元素向后移动一个位置
L[q]=L[q-1];
}
L[k]=save;// 再将剩下的空即L[k]填入save
}
i++;// 计数器加1
}
}
完整代码：
#include<stdio.h>
/* 题目：有一个顺序表L，其元素是整型数据，设计一个算法，将L中所有小于表头元素的整数放在前半部分，大于表头元素的整数放在后半部分 */
/* 打印顺序表 */
void print(int L[],int m){
printf("\n");
for(int i=0;i<m;i++){
printf("%d\t",L[i]);
}
printf("\n");
}
/* 移动元素将L中所有小于表头元素的整数放在前半部分，大于表头元素的放在后半部分（注意：没有考虑与表头元素相等的元素） */
/* L[]指的是要移动的顺序表；m指的是顺序表中元素的个数 */
void moveEle(int L[],int m){
int k=0;// 记录表头元素的下标
int temp=L[k];// 记录表头元素的值
int i=0;// 记录循环
while(i<m){
if(L[i]<temp){// 判断是否小于表头元素
int save=L[i];// 保存小于表头的元素
for(int q=i;q>0;q--){// 将L[i]之前的所有元素向后移动一个位置
L[q]=L[q-1];
}
L[k]=save;// 再将剩下的空即L[k]填入save
}
i++;// 计数器加1
}
}
int main(){
int L[]={4,3,6,8,2,1,9};
int m=7;
print(L,m);// 打印移动之前的顺序表
moveEle(L,m);// 移动元素
print(L,m);// 打印移动之后的顺序表
return 0;
} 
下面介绍下参考书上的算法：
核心代码如下：
/* 参考书解答 */
void moveEle2(int L[],int m) {
int i=0;
int j=m-1;
int temp=L[0];
while(i<j) {
while(i<j&&L[j]>temp) {
j--;
}
if(i<j) {
L[i]=L[j];
i++;
}
while(i<j&&L[i]<temp) {
i++;
}
if(i<j) {
L[j]=L[i];
j--;
}
}
L[i]=temp;
}
运行的结果和上面的算法不一样：
是由于使用的两种不同的算法移动的位置。
下面还说明一个作者参考参考书写的思路实现的代码，略微有所差别。
核心代码如下：
void moveEle3(int L[],int m) {
int i=0;// 最右边的指针
int j=m-1;// 最左边的指针
int temp=L[0];// 表头元素的值
while(i<j) {// 当i!=j时一直循环
while(L[j]>temp){// 当L[j]>temp时一直j--，j指针向前移动
j--;
}
if(L[j]<temp){// 当L[j]<temp时不再进行j--
int t=L[j];// 交换L[j]和L[i]的值
L[j]=L[i];
L[i]=t;
i++;// 并且i++
}
while(L[i]<temp) {// 当L[i]<temp时一直i++，i指针向后移动
i++;
}
if(L[i]>temp) {// 当L[i]>temp时i指针不再移动
int t=L[j];// 交换L[j]和L[i]的值
L[j]=L[i];
L[i]=t;
j--;// 并且j指针向前移动一个位置
}
}
}
运行结果如下：
