题目描述

思路分析

将集合A分为两部分，初始状态如下：

利用快速排序思想，将集合分为两部分，如下例：

因此本体主要用到快排的思想

题目解答

解题思路

由题意知，将最小的n/2（向下取整）个元素放在A1中，其余元素放在A2中，分组结果即为题目要求。仿照快排思想，基于枢轴将n个整数划分为两个子集，根据划分后去枢轴在的位置i分别处理:
（1）若i=n/2（向下取整），则分组完成算法结束
（2）若i<n/2（向下取整），则枢轴及之前的所有元素数据属于A1，继续对i之后的元素进行划分
（3）若i>n/2（向下取整），则枢轴及之后的所有元素数据属于A2，继续对i之前的元素进行划分
基于该算法无需对全部元素进行全排序。

代码实现

下面展示代码

int setPartition(int a[],int n){
	int pivotkey,low = 0,low0 = 0,high = n-1,high0 = n-1,flag = 1,k = n/2,i;
	//pivotkey为枢轴的值，low和low0初始指向数组第一个元素，high和high0初始指向数组最后一个元素，
	int s1=0,s2=0;
	while(flag){//判断要不要继续循环
	pivotkey=a[low];
	while(low<high){//进行一轮快排
		while(low<high && a[high]>=pivotkey) --hight;
		//当low的值小于high，也就是遍历数组没有结束时，
		//且high所指的数比枢轴大于或等于的时候，将high往左移，直到low=high
		if(low!=high) a[low]=a[high];//如果low不等于high，则说明此时high所指向的值小于枢轴，将值赋给low指向的位置，也就是A1部分
		//不用担心原来的low值，因为原来low所指位置的值存在了pivoykey中
		while(low<high && a[low]<=pivotkey) ++low;
		if(low!=high) a[high]=a[low];//不用担心high原来的值，因为在这次循环中high没有变动，
		//上面已经将旧的high指向的值赋给了上面新的low指向的位置的值
	 }
	 a[low]=pivotkey;//此时已退出循环，low=high，将枢轴的值赋给中间位置，也就是a[low]，这就完成一趟快排
	 if(low==k-1)//表示划分成功
	 	flag=0;
	 else{//若划分不成功，则继续划分
	 	if(low<k-1){//如果A1部分数量不到一半
	 		low0=++low;//从A2部分继续划分
	 		high=high0;
	 	}
	 	else{//如果A1部分超过一半
	 		high0=—high;//从A1部分继续划分
	 		low=low0;
	 	}
	 }
	}
	for(i=0;i<k;i++) s1+=a[i];
	for(i=k;i<n;i++) s2+=a[i];
	return s2-s1;//输出A1、A2和之差
}

时间复杂度

时间O(n) 空间O(1)

最后

以上就是忧心西装为你收集整理的2016年408数据结构算法题题目描述思路分析题目解答时间复杂度的全部内容，希望文章能够帮你解决2016年408数据结构算法题题目描述思路分析题目解答时间复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。