元素分界线

迷南。 2023-06-29 12:59 12阅读 0赞

题目描述：以第一个元素为基准，将所有小于等于它的元素移动到该元素的前面，将所有大于它的元素移动到该元素的后面。

#include<stdio.h>
    #include"sqlist.cpp"
    /*
    设计一个算法，以第一个元素为分界线，
    将所有小于它的元素移到该元素的前面，
    将所有大于它的元素移到该元素的后面。
    */
    void Move1(SqList *&L)
    {
    	int i=0,j=L->length -1;
    	//定义i和j两个指针，i指针指向第一个元素，j指针指向最后一个元素 
    	ElemType temp;
    	ElemType pivot=L->data [0];//以data[0]为基准 
    	while(i<j)//从区间两端交替向中间扫描,直至i=j为止
    	{
    		while(j>i && L->data [j]>pivot)
    			j--;//从右向左扫描,找一个小于等于pivot的元素
    		while(i<j && L->data [i]<=pivot)
    			i++;//从左向右扫描,找一个大于pivot的元素
    		if(i<j)//L->data [i] <--> L->data [j]
    		{
    			temp = L->data [i];
    			L->data [i] = L->data [j];
    			L->data [j] = temp;
    		}
    		//以下输出每一趟的结果
    		for(int k=0;k<L->length ;k++)
    		{
    			printf("%2d",L->data [k]);
    		} 
    		printf("\n");
    	}
    	//L->data [0] <--> L->data [j]
    	temp = L->data [0];
    	L->data [0] = L->data [j];
    	L->data [j] = temp;
    	printf("基准位置i=%d\n",i);
    }
    
    int main(int argc,char *argv[])
    {
    	SqList *L;
    	ElemType a[10];
    	printf("请输入10个正整数：");
    	for(int m=0;m<10;m++)
    		scanf("%d",&a[m]);
    	CreateList(L,a,10);
    	printf("L:");
    	DisplayList(L);
    	printf("执行移动运算\n");
    	Move1(L);
    	printf("L:");
    	DisplayList(L);
    	DestroyList(L);
    	return 0;
    }

解法2:

#include<stdio.h>
    #include"sqlist.cpp"
    /*
    设计一个算法，以第一个元素为分界线，
    将所有小于它的元素移到该元素的前面，
    将所有大于它的元素移到该元素的后面。
    */
    void Move2(SqList *&L)
    {
    	int i=0,j=L->length -1;
    	//定义i和j两个指针，i指针指向第一个元素，j指针指向最后一个元素 
    	ElemType pivot=L->data [0];//以data[0]为基准 
    	while(i<j)//从区间两端交替向中间扫描,直至i=j为止
    	{
    		while(j>i && L->data [j]>pivot)
    			j--;//从右向左扫描,找一个小于等于pivot的元素
    		L->data [i] = L->data [j];
    		i++;
    		while(i<j && L->data [i]<=pivot)
    			i++;//从左向右扫描,找一个大于pivot的元素
    		L->data [j] = L->data [i];
    		j--;
    		//以下输出每一趟的结果
    		for(int k=0;k<L->length ;k++)
    		{
    			printf("%2d",L->data [k]);
    		} 
    		printf("\n");
    	}
    	L->data [i] = pivot;
    	printf("基准位置i=%d\n",i);
    }
    
    int main(int argc,char *argv[])
    {
    	SqList *L;
    	ElemType a[10];
    	printf("请输入10个正整数：");
    	for(int m=0;m<10;m++)
    		scanf("%d",&a[m]);
    	CreateList(L,a,10);
    	printf("L:");
    	DisplayList(L);
    	printf("执行移动运算\n");
    	Move2(L);
    	printf("L:");
    	DisplayList(L);
    	DestroyList(L);
    	return 0;
    }