面试准备之常见上机题目搜罗（一）

左手的ㄟ右手 2022-08-26 08:11 153阅读 0赞

# 1.从考试成绩中划出及格线 #

（1）及格线是10的倍数

（2）保证至少有60%的学生及格

（3）如果有所有的学生都高于60分，则及格线为60分。

算法分析：

关键信息点为“保证至少有60%的学生及格”，可将分数线的概念转换为人数，即只需统计每个档次的人数，若60以上档次的人数就是全体人员则分数线为60，否则去寻找（由高分到低分）最先达到60%人数的档次。

java实现如下：

public class Exam{
    	public int findPassLine(int[] scores){
    		int num=scores.length;
    		int[] record=new int[num+1];//记录每一个档次的人数
    		for(int i=0;i<num;i++){
    		  switch(scores[i]/10){
    		  	case 10:record[10]++;break;
    		  	case 9:record[9]++;break;
    		  	case 8:record[8]++;break;
    		  	case 7:record[7]++;break;
    		  	case 6:record[6]++;break;
    		  	case 5:record[5]++;break;
    		  	case 4:record[4]++;break;
    		  	case 3:record[3]++;break;
    		  	case 2:record[2]++;break;
    		  	case 1:record[1]++;break;
    		  	case 0:record[0]++;break;
    		  }
    	  }
    	  int sumh=0;//记录60分以上所有人数
    	  int suml=0;//记录60分以下所有人数
    	  for(int j=record.length-1;j>=0;j--){
    	  	if(j>=6)
    	  	 sumh+=record[j];
    	  }
    	  suml=10-sumh;
      	if(sumh==10){//所有人都在60分以上
    	  		System.out.println("所有人的分数均高于60，分数线为：");
    	  		return 60;
    	  }
    	  else{
    	  	//有高分档次向下遍历
    		  for(int k=record.length-1;k>0;k--){//10~0遍历
    		   	if(record[k]>=6){
    		   			return 10*k;	  
    		   	}
    		   	else
    		   	 record[k-1]+=record[k];//向下累加
    		  }
    	  }
    	  return 0;
    	}
    	
    	public static void main(String[] args){
    	  int a[]={99,89,79,69,0,0,4,5,80,50};
    	  System.out.println(new Exam().findPassLine(a));
    	  int b[]={100,100,100,100,100,80,0,0,0,0};
    	  System.out.println(new Exam().findPassLine(b));
    	  int c[]={100,100,100,100,100,100,0,0,0,0};
    	  System.out.println(new Exam().findPassLine(c));
    	  int d[]={100,100,100,100,100,100,60,80,70,90};
    	  System.out.println(new Exam().findPassLine(d));
    	}
    }

输出：

50  
80  
100  
所有人的分数均高于60，分数线为：  
60

# 2.亮着电灯的盏数 #

一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯，从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始，电灯全部关着。  
    有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下；接着第二个学生把号码凡是2的倍数的电灯的开关拉一下；接着第三个学生把号码凡是3的倍数的电灯的开关拉一下；如此继续下去，最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后，长廊里电灯有几盏亮着。  
注：电灯数和学生数一致。

算法分析：无任何算法可言，只需要按照题目描述实现一边，不知道有啥捷径

java实现如下：

//import java.lang.StringBuilder;
    public class Light{
    	
    	public int lightNum(int[] lights){
    		//刚开始默认全部打开，1开，0闭
    		int i=1,n=lights.length-1,num=0;
    		while(i<=n){
    			for(int j=1;j<=n;j++){//遍历1--n栈灯(0号元素忽略)
    				if(j%i==0){
    					if(lights[j]==1){
    						//开着的等被关闭
    						lights[j]=0;
    						num--;
    					}
    					else if(lights[j]==0) {
    						//关闭的灯被打开
    					 	lights[j]=1;
    						num++;
    					}
    			  }
    			}	
    			i++;//第i个人
    		}
    		return num;
    	}
    	//打印亮着的编号
    	public void printLightsNum(int[] lights){
    		StringBuilder sb=new StringBuilder();
    		sb.append("它们分别是:");
    		for(int i=1;i<=lights.length-1;i++){
    			if(lights[i]==1){//开着
    				sb.append(" ");
    				sb.append(i);
    			}
    		}
    		System.out.println(sb.toString());
    	}
    	
    	public static void main(String[] args){
    		for(int i=10;i<=100;i+=10){
    			System.out.println("初始时"+i+"栈灯灭着!");
    			int[] lights=new int[i+1];
    			Light obj=new Light();
    			System.out.println("触动后还剩下"+obj.lightNum(lights)+"栈灯开着！");
    			obj.printLightsNum(lights);
    			System.out.println("--------------------------------------------------");
    	  }
    	}
    
    }

输出：

初始时10栈灯灭着!  
触动后还剩下3栈灯开着！  
它们分别是: 1 4 9  
\--------------------------------------------------  
初始时20栈灯灭着!  
触动后还剩下4栈灯开着！  
它们分别是: 1 4 9 16  
\--------------------------------------------------  
初始时30栈灯灭着!  
触动后还剩下5栈灯开着！  
它们分别是: 1 4 9 16 25  
\--------------------------------------------------  
初始时40栈灯灭着!  
触动后还剩下6栈灯开着！  
它们分别是: 1 4 9 16 25 36  
\--------------------------------------------------  
初始时50栈灯灭着!  
触动后还剩下7栈灯开着！  
它们分别是: 1 4 9 16 25 36 49  
\--------------------------------------------------  
初始时60栈灯灭着!  
触动后还剩下7栈灯开着！  
它们分别是: 1 4 9 16 25 36 49  
\--------------------------------------------------  
初始时70栈灯灭着!  
触动后还剩下8栈灯开着！  
它们分别是: 1 4 9 16 25 36 49 64  
\--------------------------------------------------  
初始时80栈灯灭着!  
触动后还剩下8栈灯开着！  
它们分别是: 1 4 9 16 25 36 49 64  
\--------------------------------------------------  
初始时90栈灯灭着!  
触动后还剩下9栈灯开着！  
它们分别是: 1 4 9 16 25 36 49 64 81  
\--------------------------------------------------  
初始时100栈灯灭着!  
触动后还剩下10栈灯开着！  
它们分别是: 1 4 9 16 25 36 49 64 81 100  
\--------------------------------------------------

从输出中反推原理：最后亮着灯的编号都是可以开方的数，这时为什么呢？

题中告知所有灯刚开始是关着的，也就说最后想开着，必须触动开关奇数次，即"该灯所对应的编号数，其公约数有奇数个"。那么问题就转化为"什么样的数有奇数个公约数",由于已经知道答案了(完全平方数)，所有只好用反证法。

证：   若对任意实数C具有奇数个公约数，且C不是完全平方数

则有C的任意一对公约数m1!=m2，设C有n对公约数，

则C的公约数总数=n\*2+2(可以被自身和1整除)=2\*(n+1)为偶数

此结论与已知"C具有奇数个公约数"矛盾，故C是完全平方数。

有了上面的结论，即可以直接去找1--n内的完全平方数即可,复杂度就降为O(n)了，我想这就是华为将此题做为中级难度题目的捷径思路了吧。

# 3.验证括号是否匹配 #

输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘\[’,'\]'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.  
Smple input：dfa(sdf)df\[dfds(dfd)\]    Smple outPut:0

算法分析：利用栈来实现，所有左括号入栈，遇到右括号就进行出栈，看是否匹配。

java实现：

import java.util.Scanner;
    import java.util.Stack;
    public class Match{
    	public static void main(String[] args){
    		Boolean isMatch=true;
    		Stack<Character> stack=new Stack<Character>();
    		Scanner s=new Scanner(System.in);
    		while(true){
    			char ch=s.nextLine().charAt(0);
    			if(ch=='q')
    			  break;
    			else{
    						switch(ch){
    							case '{':;
    							case '[':;
    							case '(':
    								stack.push(ch);break;
    							case '}':
    								if(stack.empty())
    									isMatch=false;
    								else if(stack.pop()!='{')
    									isMatch=false;
    									break;
    							case ']':
    									if(stack.empty())
    									isMatch=false;
    								else if(stack.pop()!='[')
    									isMatch=false;
    									break;
    							case ')':
    								if(stack.empty())
    									isMatch=false;
    								else if(stack.pop()!=')')
    									isMatch=false;
    									break;
    						}
    				}
    		}
    		if(isMatch)
    			System.out.println("匹配！");
    		else
    			System.out.println("不匹配");
    	}
    }

C/C++:

void main()  
    13.{//子函数声明   
    14.    void InitStack(SqStack &S);//初始化空栈   
    15.    int StackEmpty(SqStack S);//判空   
    16.    void push(SqStack &S,int e);//进栈   
    17.    void pop(SqStack &S,int &e);//出栈   
    18.    //主函数开始   
    19.    SqStack s;//初始化空栈   
    20.    InitStack(s);  
    21.    char ch[100],*p;int e;  
    22.    p=ch;  
    23.    printf("输一个含义有()[]{}的括号表达式:\n");  
    24.    gets(ch);  
    25.    while(*p)  
    26.    {   
    27.        switch (*p)  
    28.        {  
    29.        case '{':  
    30.        case '[':  
    31.        case '(': push(s,*p++);break;//只要是左括号就入栈   
    32.        case '}':  
    33.        case ']':  
    34.        case ')':pop(s,e);  
    35.                 if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')'))  
    36.                 p++;  
    37.                 else  
    38.                 {printf("括号不匹配!");exit(OVERFLOW);}  
    39.                 break;  
    40.        default :p++;//其他字符就后移   
    41.        }  
    42.    }  
    43.    if (StackEmpty(s))  
    44.      printf("括号匹配成功");  
    45.    else  
    46.      printf("缺少右括号！");  
    47.    printf("\n");  
    48.}

# 4.回文数 #

判断回文数，是返回1  
    算法分析：既然是对称的，那么从个位开始，逆序反向生成一个数，若该数与原数相同，则是回文数。

Scanner s=new Scanner(System.in);
    		  int num=s.nextInt();
    		  int max=num,min=0;
    		  while(max>0){
    		  	min=min*10+max%10;//反向生成
    		  	max=max/10;//去除最后一位
    		  }
    		  if(min==max)
    		  	System.out.println("Yes");
    		  else
    		    System.out.println("No");

附：回文数还有一个性质，即数字位数与存在的回文数有如下关系，

1位回文数： 9个

2位回文数： 9个

3位回文数： 90个

4位回文数： 90个

5位回文数： 900个

6位回文数： 900个

…

即每增加两位，则存在的回文数为原来的10倍。

# 5.将整数倒序输出，剔除重复数据 #

输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输出，最后如果是0，则不输出，输出的数字是不带重复数字的，所以上面的输出是456321和571。如果是负数，比如输入-175，输出-571。  
    算法分析：将每一位存储，存储时剔除重复元素，而后输出。（注意符号）

public static void main(String[] args){	
    	 Scanner s=new Scanner(System.in);
    		  int num=s.nextInt();
    		  int[] store=new int[]{99,99,99,99,99,99,99,99,99,99,99,99,99};//初始值不要赋个位数，避免和取余后的数等值
    		  int len=0,tmp=num,last;
    		  while(true){
    		  	if(tmp==0)
    		  		break;
    		  	else{
    					  	int lastNum= tmp%10;//取余求最后一位
    					  	tmp=tmp/10;
    					  	int flag=1;//待插入数组中是否含有该数
    					  	for(int k=0;k<=len;k++){
    					  		if(store[k]==lastNum){
    					  			flag=0;//重复则不插入
    					  			break;
    					  		}
    					  	}
    					  	if(flag!=0){
    					  		store[len]=lastNum;//需要插入
    					  		len++;
    					  	}
    		 	 }
    		  }
    		  //len指向待插入位置
    		  if(num<0)
    		  		System.out.print("-");
    		  for(int j=0;j<len;j++){
    		  	if(store[j]!=0)
    		  	System.out.print(Math.abs(store[j]));
    		  }
    	}

#  6.大数相减 #

输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。

备注：1、两个整数都是正整数，被减数大于减数

示例：

输入：1000000000000001

输出：1000000000000000

注意大数用char a\[\] 存储，用%s接收，一位一位的运算。注意a\[0\]里的正负号

算法描述：一位一位减，最高位无需借位。不仅可以大减小，也可以小减大(大减小取负即可)。

java实现：

public int[] subtraction(int[] a,int[] b){
    		int[] c=new int[a.length];
    		//a[0]...a[n]代表高位到低位
    		for(int i=c.length-1;i>=0;i--){
    			//最高位不借位
    			if(i!=0){
    					if(a[i]<b[i]){
    						a[i-1]-=1;//向高位借位
    						a[i]+=10;
    					}	
    			}
    			c[i]=a[i]-b[i];//存储对应位的差值
    		}
    		return c;
    	}

输出：

2 7 8 7 1 0 0 2 9 4 0 7 0 8 3 3 8 7 0 6  
\-   2 5 1 3 7 3 8 8 8 3 1 7 5 2 3 7 3 6 1 2  
\----------------------------------------------------  
    0 2 7 3 3 6 1 4 1 0 8 9 5 5 9 6 5 0 9 4

0 8 4 9 2 7 2 5 7 8 4 8 1 3 1 0 6 1 7 9  
\-   2 0 2 1 6 0 4 9 2 8 8 0 6 3 3 0 2 0 5 8  
\----------------------------------------------------  
   -1 1 7 2 3 3 2 3 5 0 3 2 5 0 1 9 5 8 7 9

6 6 5 5 5 1 1 1 5 6 5 5 1 6 2 1 9 7 2 9  
\-   0 2 8 5 9 7 5 8 9 8 2 8 0 1 8 5 7 3 3 4  
\----------------------------------------------------  
    6 3 6 9 5 3 5 2 5 8 2 7 1 4 3 6 2 3 9 5

3 4 7 5 7 1 1 1 9 1 9 2 2 0 0 4 5 2 9 8  
\-   5 9 5 6 1 5 8 9 8 9 7 1 9 7 1 2 5 0 3 5  
\----------------------------------------------------  
   -2 4 8 0 4 4 7 7 9 7 7 9 7 7 0 7 9 7 3 7

5 1 9 0 4 6 1 6 1 6 5 3 1 9 9 3 8 5 9 5  
\-   4 0 2 2 8 3 3 4 8 0 9 0 3 5 5 8 3 1 5 0  
\----------------------------------------------------  
    1 1 6 7 6 2 8 1 3 5 6 2 8 4 3 5 5 4 4 5

完整代码：

import java.util.Random;
    public class Sub{
    	
    	
    	
    	//判别大小
    	public Boolean compare(int[] a,int[] b){
    		Boolean bool=true;//大于
    		for(int i=0;i<a.length;i++){
    			//从高位开始遍历
    			if(a[i]<b[i]){
    				bool=false;
    				break;
    			}
    			else if(a[i]>b[i]){
    				bool=true;
    				break;
    			}
    		}
    		return bool;
    	}
    	
    	
    	
    	public int[] subtraction(int[] a,int[] b){
    		int[] c=new int[a.length];
    		//a[0]...a[n]代表高位到低位
    		for(int i=c.length-1;i>=0;i--){
    			//最高位不借位
    			if(i!=0){
    					if(a[i]<b[i]){
    						a[i-1]-=1;//向高位借位
    						a[i]+=10;
    					}	
    			}
    			c[i]=a[i]-b[i];//存储对应位的差值
    		}
    		return c;
    	}
    	//输出
    	public void print(int[] bt){
    		for(int b : bt){
    			System.out.print(b+" ");
    	  }
    	  
    	 
    	}
    	
    	public static void main(String[] args){
    		
    		Random rand=new Random();
    		for(int i=0;i<5;i++){
    			Sub sub=new Sub();
    			int[] a=new int[20];
    			int[] b=new int[20];
    			for (int n=0; n<a.length; n++) {
    			 	a[n]=rand.nextInt(10);//随机0--9
    			 	b[n]=rand.nextInt(10);
    			} 
    			System.out.print("    ");
    			sub.print(a);
    			System.out.println("");
    			System.out.print("-   ");
    			sub.print(b);
    			System.out.println("");
    			System.out.println("------------------------------------------------");
    			if(sub.compare(a,b)){//保证被减数大于减数
    				System.out.print("    ");
    				sub.print(sub.subtraction(a,b));
    				System.out.println("");
    			}
    			else{
    				System.out.print("   -");
    				sub.print(sub.subtraction(b,a));
    				System.out.println("");
    			}
    				 System.out.println("");
    				 System.out.println("");
    		}
    				
    		  		
    		 
    	}
    }

#  7.上海华为的一道关于指针方面的编程题 #

题目：

int A\[nSize\]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int\* A, int nSize)，使A把0移至后面，非0整数移至 数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)

思路：  
     选择一个排序算法对其进行排序，在排序过程中记录0元素的个数count，即nSize-count为首个0元素的下标；需要注意的是，若排序时需由大到小的排序（题中只说保持有序），不然0元素出现在前半部分又要移动元素。

C实现如下：

#include <stdio.h>
    using namespace std;
    int Func(int *A,int nSize){
    	if(A!=0&&nSize>0){
    		int count=0;//记录0元素的个数
    		//折半插入排序
    		int low,high,mid;
    		if(*A==0)
    			count++;
    		for(int i=1;i<nSize;i++){
    			low=0;
    			high=i-1;
    			mid=(low+high)/2;
    			while(low<=high){
    				if(*(A+i)>*(A+mid))//key>mid
    					high=mid-1;//注意此处故意倒序排列
    				else
    					low=mid+1;
    				mid=(low+high)/2;
    			}
    			//high+1为待插入位置
    			int key=*(A+i);
    			//后移元素腾出位置
    			for(int j=i;j>high+1;j--){
    				*(A+j)=*(A+j-1);
    			}
    			*(A+high+1)=key;//插入
    
    			if(key==0)
    				count++;
    		}
    		return nSize-count;
    	}
    	else
    		return -1;
    }
    
    void main(){
    	int a[]={0,3,0,4,9,1,0,44,2,0,12};
    	int index=Func(a,11);
    	printf("首个0在 %d 处\n",index);
    	for(int i=0;i<11;i++){
    		printf("%d ",a[i]);
    	}
    }

输出：

首个0在 7 处  
44 12 9 4 3 2 1 0 0 0 0 请按任意键继续. . .

# 8.素数问题 #

题目：  
     求2~2000的所有素数.有足够的内存,要求尽量快  
思路：  
     查表法，即为2~2000的序列建立对应的表，表大小与序列大小一致(序列需要由小到大排序)，选择最小的素数并将其倍数剔除(在表中记录),在剩余的序列中，继续选择最小的素数并剔除其倍数，直到剔除到第N个。这样的好处在于每次遍历时可以参考上次table中的标记，可以避免许多重复操作。  
     例如在判断4是否为素数时，由于在剔除2的倍数时在表中已经标记为NONPRIME（不是素数），那就不比调用判断素数的方法，省去许多操作。

C实现，为了输出方便，选择10以内的素数

#include <stdio.h>
    #include <math.h>
    #define TRUE 1
    #define FALSE 0
    #define NULL -1   //未遍历标记
    #define NONPRIME 0//不是素数标记
    #define PRIME 1   //是素数标记
    #define LEN 10+1  //为了让数组下标一致
    using namespace std;
    
    int isPrime(int num){
    	if(num==2)
    		return TRUE;
    	for(int i=2;i<=sqrt((double)num);i++){
    		if(num%i==0)
    			return FALSE;
    	}
    	return TRUE;
    }
    //将num的倍数剔除（num为最小质数）
    void deleNonPrime(int table[], int num){
    	table[num]=PRIME;
    	for(int i=2*num;i<LEN;i+=num){
    		
    		if(table[i]==NULL){//有可能已经被赋值了
    		   table[i]=NONPRIME;
    		}
    	}
    }
    
    void print(int arr[],int size){
    	for(int i=2;i<size;i++){
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    
    }
    
    void main(){
    	int primes[LEN]={NULL};
    	int table[LEN]={NULL};//建立对应的表
    	for(int i=2;i<LEN;i++){
    		primes[i]=i;
    		table[i]=NULL;
    	}
    	for(int j=2;j<LEN;j++){
    		if(j==2){
    			deleNonPrime(table,2);
    		}
    		else{//参考上次表中的标记
    			if(table[j]==NULL){//有可能为素数（剔除时有可能已经判断过了，避免重复判断）
    				if(isPrime(primes[j])){
    					deleNonPrime(table,primes[j]);
    				}
    			}
    		}
    		printf("序列：");
    		print(primes,LEN);
    		printf("  表：");
    		print(table,LEN);
    		printf("\n\n");
    
    	}
    	for(int i=2;i<LEN;i++){
    		if(table[i]==PRIME)
    		  printf("%d ",i);
    	}
    
    }

输出：

序列：2 3 4 5 6 7 8 9 10  
  表：1 -1 0 -1 0 -1 0 -1 0

序列：2 3 4 5 6 7 8 9 10  
  表：1 1 0 -1 0 -1 0 0 0

序列：2 3 4 5 6 7 8 9 10  
  表：1 1 0 1 0 -1 0 0 0

序列：2 3 4 5 6 7 8 9 10  
  表：1 1 0 1 0 1 0 0 0

2 3 5 7 请按任意键继续. . .

注意isPrime函数判断素数时只用判断至sqrt处(素数定理)。

# 9.操作系统任务调度问题 #

题目：

操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。优 先级大于255的为非法任务，应予以剔除。现有一任务队列task\[\]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler 实现如下功能，将task\[\] 中的任务按照系统任务、用户任务依次存放到 system\_task\[\] 数组和 user\_task\[\] 数组中（数组中元素的值是任务在task\[\] 数 组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。  
 例如：  
     task\[\] = \{0, 30, 155, 1, 80, 300, 170, 40, 99\}  
     system\_task\[\] = \{0, 3, 1, 7, -1\}  
     user\_task\[\] = \{4, 8, 2, 6, -1\}  
     函数接口 void scheduler(int task\[\], int n, int system\_task\[\], int user\_task\[\])

思路：

先以50做为关键字对原有序列进行一次快排，返回50的待插入位置location即为系统任务的个数，然后以location做为分界线，左右两边分别进行快排，最后依次将左半部放在system\_task\[\]中，右半部分放在user\_task\[\]（需剔除大于255的）

C/C++实现如下：

#include <stdio.h>
    using namespace std;
    // 利用一趟快速排序找分界线的位置i,即[low,i)为系统任务，[i,high]为用户任务
    int findLine(int task[],int lowSpace,int highSpace,int key){
    	int low=lowSpace,high=highSpace;
    	while(low<high){
    	
    		while(low<high&&task[high]>key){
    			high--;
    		}
    		if(low<high){
    			int tmp=task[high];
    			task[high]=task[low];
    			task[low]=tmp;
    		}
    		while(low<high&&task[low]<key){
    			low++;
    		}
    		if(low<high){
    			int tmp=task[low];
    			task[low]=task[high];
    			task[high]=tmp;
    		}
    		
    	}
    	return low;
       
    }
    
    void quickSort(int subTask[],int lowSpace,int highSpace){
    	
    	if(lowSpace<highSpace){//限制递归
    		int low=lowSpace,high=highSpace;
    		int insertIndex;//待插入位置
    		int key=subTask[lowSpace];//关键字
    		while(low<high){
    	
    			while(low<high&&subTask[high]>=key){
    				high--;
    			}
    			if(low<high){
    				int tmp=subTask[high];
    				subTask[high]=subTask[low];
    				subTask[low]=tmp;
    			}
    			while(low<high&&subTask[low]<=key){
    				low++;
    			}
    			if(low<high){
    				int tmp=subTask[low];
    				subTask[low]=subTask[high];
    				subTask[high]=tmp;
    			}
    		
    		}
    		insertIndex=low;
    		subTask[insertIndex]=key;
    		if(insertIndex==lowSpace)
    			quickSort(subTask,insertIndex+1,highSpace);//只用排高区
    		else if(insertIndex==highSpace)
    			quickSort(subTask,lowSpace,insertIndex-1);//只用排低区
    		else {
    			quickSort(subTask,lowSpace,insertIndex-1);
    			quickSort(subTask,insertIndex+1,highSpace);
    		}
    	}
    }
    
    void scheduler(int task[], int n, int system_task[], int user_task[]){
    	int index=findLine(task,0,n-1,50);//以50为关键字划分
    	//分别排序
    	quickSort(task,0,index);
    	quickSort(task,index+1,n-1);
    	int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index
    	for(int i=0;i<n;i++){
    		//系统任务[0,index)
    		if(i<=index){
    			system_task[i]=i;
    		}
    		//用户任务[index,n)
    		else if(i>index){
    			//剔除无效任务
    			 if(task[i]>=50&&task[i]<=255){
    				user_task[i-index-1]=i;
    				len++;
    		     }
    			
    
    		}
    		
    		
    	}
    	system_task[index+1]=-1;//结束
    	user_task[len]=-1;
    
    
    }
    
    void printArr(int task[],int n){
    	for(int i=0;i<n;i++){
    	  printf("%d ",task[i]);
    	}
    	printf("\n");
    }
    //测试
    void main(){
    	int task[]={0, 30, 155, 1, 80, 300, 170, 40, 99};
    	int system_task[9]={-1};
    	int user_task[9]={-1};
    	scheduler(task,9,system_task,user_task);
    	printf("排序完成后总任务为：\n");
    	printArr(task,9);
    	printf("系统任务为：\n");
    	printArr(system_task,9);
    	printf("用户任务为：\n");
    	printArr(user_task,9);
    }

输出：

排序完成后总任务为：  
0 1 30 40 80 99 155 170 300  
系统任务为：  
0 1 2 3 -1 0 0 0 0  
用户任务为：  
4 5 6 7 -1 0 0 0 0  
请按任意键继续. . .

突然发现自己把题意弄错了，我虽然实现了任务分离和任务，但是题目输出的是原始索引坐标，并不是排序后的。为了实现寻找原始索引，引入一个索引表，只要任务元素被移动，则table的索引随之移动，最后只要查表即可。

C\#实现如下：

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace 控制台编程练习
    {
        class 任务分配
        {
        //寻找关键字的分界线
        int findLine(int[] task,int lowSpace,int highSpace,int key,int[] table){
    	    int low=lowSpace,high=highSpace;
    	    while(low<high){
    	
    		    while(low<high&&task[high]>key){
    			    high--;
    		    }
    		    if(low<high){
                    swap(high, low, task);
                    swap(high, low, table);
    		    }
    		    while(low<high&&task[low]<key){
    			    low++;
    		    }
    		    if(low<high){
                    swap( low,high ,task);
                    swap(low, high, table);
    		    }
    		
    	    }
    	    return low;
       
    }
    //交换
    void swap(int a,int b,int[] task){
    	int tmp= task[a];
    	task[a]=task[b];
    	task[b]=tmp;
    }
    //快排
    void quickSort(int[] subTask,int lowSpace,int highSpace,int[] index){
    	
    	if(lowSpace<highSpace){//限制递归
    		int low=lowSpace,high=highSpace;
    		int insertIndex;//待插入位置
    		int key=subTask[lowSpace];//关键字
            int table_key = index[lowSpace];//表索引虚拟关键字
    		while(low<high){
    	
    			while(low<high&&subTask[high]>=key){
    				high--;
    			}
    			if(low<high){
    				swap(high,low,subTask);
    				swap(high,low,index);
    			}
    			while(low<high&&subTask[low]<=key){
    				low++;
    			}
    			if(low<high){
    				swap(low,high,subTask);
    				swap(low,high,index);
    			}
    		
    		}
    		insertIndex=low;
    		subTask[insertIndex]=key;
    		index[insertIndex]=table_key;//索引表也要变动
    		if(insertIndex==lowSpace)
    			quickSort(subTask,insertIndex+1,highSpace,index);//只用排高区
    		else if(insertIndex==highSpace)
    			quickSort(subTask,lowSpace,insertIndex-1,index);//只用排低区
    		else {
    			quickSort(subTask,lowSpace,insertIndex-1,index);
    			quickSort(subTask,insertIndex+1,highSpace,index);
    		}
    	}
    }
    //建立索引表
    int[] creatTable(int n)
    {
        int[] table = new int[n];
        for (int i = 0; i < n; i++)
        {
            table[i] = i;
        }
        return table;
    }
    
    void scheduler(int[] task, int n, int[] system_task, int[] user_task){
        int[] table = creatTable(n);
        int index = findLine(task, 0, n - 1, 50, table);//以50为关键字划分
    	//分别排序
    	quickSort(task,0,index,table);
    	quickSort(task,index+1,n-1,table);
    	int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index
    	for(int i=0;i<n;i++){
    		//系统任务[0,index)
    		if(i<=index){
    			system_task[i]=table[i];
    		}
    		//用户任务[index,n)
    		else if(i>index){
    			//剔除无效任务
    			 if(task[i]>=50&&task[i]<=255){
    				user_task[i-index-1]=table[i];
    				len++;
    		     }
    		}
    	}
    	system_task[index+1]=-1;//结束
    	user_task[len]=-1;
    }
    
    void printArr(int[] task,int n){
    	for(int i=0;i<n;i++){
    	  Console.Write(task[i]+" ");
    	}
        Console.WriteLine();
    }
    
        static void Main()
        {
            任务分配 s = new 任务分配();
            int[] task={0, 30, 155, 1, 80, 300, 170, 40, 99};
    	    int[] system_task=new int[9];
    	    int[] user_task=new int[9];
            Console.WriteLine("原始任务为:");
            s.printArr(task,9);
            s.scheduler(task, 9, system_task, user_task);
            Console.WriteLine("系统任务为:");
            s.printArr(system_task, 9);
            Console.WriteLine("用户任务为:");
            s.printArr(user_task, 9);
        }
      }
    }

输出：

原始任务为:  
0 30 155 1 80 300 170 40 99  
系统任务为:  
0 3 1 7 -1 0 0 0 0  
用户任务为:  
4 8 2 6 -1 0 0 0 0  
请按任意键继续. . .

# 10.奇偶插入排序 #

题目：  
     对一个数组，将数组中偶数从大到小排序，奇数从小到大排序,奇数和偶数交叉着放且输出数组第一位放奇数若奇数和偶数不等长，则把剩下的直接放到数组中。  
思路：  
     将奇数和偶数元素分别存放，然后分别排序，最后一起交叉填充(覆盖)到原数组。

C/C++实现如下：

#include<stdio.h>
    #include<malloc.h>
    #define DEFAULT 0
    #define low_to_high 0//由小到大
    #define high_to_low 1//由大到小
    using namespace std;
    
    //折半插入排序
    void halfSort(int *a,int n,int type){
    	for(int i=1;i<n;i++){
    		int high=i-1;
    		int low=0;
    		int mid=(high+low)/2;
    		int key=a[i];//待排关键字
    		//寻找位置
    		if(type==low_to_high){
    			while(low<=high){
    				if(a[mid]<key)
    					low=mid+1;
    				else
    					high=mid-1;
    				mid=(low+high)/2;
    			}
    		}
    		else{
    			while(low<=high){
    				if(a[mid]<key)
    					high=mid-1;
    				else
    					low=mid+1;
    				mid=(low+high)/2;
    			}
    		}
    		//插入位置在high+1，全体移动a[high+1]...a[i]
    		for(int j=i;j>high+1;j--){
    			a[j]=a[j-1];
    		}
    		a[high+1]=key;
    	}
    }
    
    void print(int *a,int n){
    	for(int i=0;i<n;i++){
    		printf("%d ",*(a+i));
        }
    	/*while(*a!='\0'){
    		printf("%d ",*a++);
    	}*/
    	printf("\n");
    }
    
    
    void oddAndEvenSort(int a[],int n){
    	int odd[10]={0};
    	int even[10]={0};
    	int evenCount=0;//偶数个数
    	int oddCount=0;
    	for(int i=0;i<n;i++){
    		if(a[i]%2==0){
    			even[evenCount]=a[i];
    		
    			evenCount++;
    		}
    		else{
    			odd[oddCount]=a[i];
    			
    			oddCount++;
    		}
    	}
    	
    	halfSort(odd,oddCount,low_to_high);
    	halfSort(even,evenCount,high_to_low);
    	if(oddCount==0){
    		print(even,evenCount);
    	}
    	else if(evenCount==0){
    		print(odd,oddCount);
    	}
    	else if(oddCount<evenCount){
    		for(int i=0;i<oddCount;i++){
    			a[2*i]=odd[i];
    			a[2*i+1]=even[i];
    		}
    		for(int j=oddCount;j<n;j++){//剩余偶数补全
    			a[j+oddCount]=even[j];
    		}
    		print(a,n);
    	}
    	else if(oddCount==evenCount){
    		for(int i=0;i<oddCount;i++){
    			a[2*i]=odd[i];
    			a[2*i+1]=even[i];
    		}
    		print(a,n);
    	}
    		
    	else if(oddCount>evenCount){
    		for(int i=0;i<evenCount;i++){
    			a[2*i]=odd[i];
    			a[2*i+1]=even[i];
    		}
    		for(int j=evenCount;j<n;j++){//剩余奇数补全
    			a[j+evenCount]=odd[j];
    		}
    		print(a,n);
    	}
    
    
    }
    
    void main(){
    	int a1[]={2,4,6,8,10,12,14,16,18,1};
    	oddAndEvenSort(a1,10);
    	int a2[]={2,4,6,8,10,1,3,5,7,9};
    	oddAndEvenSort(a2,10);
    	int a3[]={2,4,6,1,3,5,7,9,11,13};
    	oddAndEvenSort(a3,10);
    
    }

输出：

1 18 16 14 12 10 8 6 4 2  
1 10 3 8 5 6 7 4 9 2  
1 6 3 4 5 2 7 9 11 13

**总结：又没仔细看题，偶数元素是从大到小，奇数是从小到大排序，题目虽简，但也须仔细认真，切记。**