第五周习题

﹏ヽ暗。殇╰゛Y 2022-11-16 10:37 246阅读 0赞

### 我只是记录一下啦 ###

*  A、冒泡排序
 *   *  我的自白
     *   *  代码
 *  B、用二分搜索试试
 *   *  我的自白
     *   *  代码
 *  C、随机数
 *   *  我的自白
     *   *  代码
 *  D、整数奇偶排序
 *   *  我的自白
     *   *  代码
 *  E、快速排序
 *   *  我的自白
     *   *  代码
 *  F、随机化快速排序
 *   *  我的自白
     *   *  代码

# A、冒泡排序 #

**题目描述**

*  从键盘上输入10个整数，用冒泡法对这10个数进行排序（由小到大）。【必须使用冒泡排序实现】

**输入**

*  以空格分隔的10个整数

**输出**

*  依次输出排好序的10个整数，每个数占一行。

**样例输入 Copy**

1 3 5 7 9 2 4 6 8 0

**样例输出 Copy**

0
    1
    2
    3
    4
    5
    6
    7
    8
    9

## 我的自白 ##

*  【冒泡排序，就是不断做比较，这个，我写的时候发现我之前写过一个一样的，然后我就直接ctrl+c加ctrl+v了，广大朋友们，绝对不要学我，没有好处，真的！更让我觉得我真的是太绝了，我还忘了我是不是记录过一次了，啊——————】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int temp;
    		int []a = new int[20];
    		while(sc.hasNext()){ 
    			for(int i=0;i<10;i++)
    				a[i] = sc.nextInt();			
    			for(int i=0;i<10;i++)
    				for(int j=0;j<10-i-1;j++)
    					if(a[j]>a[j+1])
    					{ 
    						temp=a[j];
    						a[j]=a[j+1];
    						a[j+1]=temp;
    					}
    			for(int i=0;i<10;i++)
    				System.out.println(a[i]);
    		}
    
    	}
    
    }

# B、用二分搜索试试 #

**题目描述**

*  请编写一个程序，输入包含n（n<=100000）个整数的数列S以及包含q个(q<=50000)不重复整数的数列T，输出既包含于T也包含于S的整数的个数C。S、T中的元素均大于0且小于109。S的元素按升序排列，T的元素不重复。

**输入**

*  第一行输入n，第二行输入代表S的n个整数，第三行输入q，第四行输入代表T的q个整数。

**输出**

*  用1行输出C。

**样例输入 Copy**

5
    1 2 3 4 5
    3
    3 4 1

**样例输出 Copy**

## 我的自白 ##

*  【上周的练习题中，是用线性搜索做的，那是选择了T数组的值作为KEY值，然后和S数组的值比较，相等的话就计数，然后用二分搜索的话，我就直接调用了二分搜索的这个函数，上周的练习题中也有二分搜索，我把上周练习题的链接放在这里吧：[二分搜索还有线性搜索都在这个链接这里咯][Link 1]】

### 代码 ###

如果有什么不对的地方，还请一定要告诉我呢!

import java.util.Scanner;
    
    public class Main { 
    	public static int cbb(int shuzu[], int key) { 
            int mid = shuzu.length / 2;
            if (key == shuzu[mid]) { 
                return mid+1;
            }
     
            int low= 0;
            int high = shuzu.length - 1;
            while (low<= high) { 
                mid = (high - low) / 2 + low;
                if (key < shuzu[mid]) { 
                    high = mid - 1;
                } else if (key > shuzu[mid]) { 
                    low = mid + 1;
                } else { 
                    return mid+1;
                }
            }
            return -1;
        }
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		int bb[]= new int[1000];
    		while(sc.hasNext()){ 
    			
    			int n = sc.nextInt();
    			int S[] = new int[n];
    			for(int i=0;i<n;i++)
    				S[i] = sc.nextInt();
    			
    			
    			int q = sc.nextInt();
    			int T[] = new int[q];
    			for(int i=0;i<q;i++)
    				T[i] = sc.nextInt();
    			int geshu = 0;
    			for(int i=0;i<q;i++)
    				if(cbb(S,T[i])!=-1){ 
    					geshu++;
    				}							
    				System.out.println(geshu);	
    			}
    				
    		}
    }

# C、随机数 #

**题目描述**

*  有一个rand(n)的函数，它的作用是产生一个在\[0,n)的随机整数。现在有另外一个函数，它的代码如下：

int random(int n, int m)
    
    { 
    
             return rand(n)+m;
    
    }

*  显而易见的是函数random(n,m)可以产生任意范围的随机数。现在问题来了，如果我想要产生范围在\[a,b)内的一个随机数，那么对应的n，m分别为多少？

**输入**

*  输入的第一行为一个正整数T (T<=1000)，表示一共有T组测试数据。
 *  对于每组测试数据包含两个整数a，b (a<=b)。

**输出**

*  对于每组测试数据，输出一行包含两个整数n和m，两个整数中间有一个空格分隔。

**样例输入 Copy**

2
    0 5
    1 4

**样例输出 Copy**

5 0
    3 1

## 我的自白 ##

*  【[算法分析与设计，这个是我当时找到的代码，因为不会，其实我是真的没有太搞懂，话说，我都没搞懂，写在这里是不是会误人子弟啊，好吧，我就先记录一下哈，大家有需要去原作者哪里看看这个随机数的代码呀，记得点击蓝色的字体，就是这个 哟~反正不要学我，一定要把题目搞懂哟][Link 2]】

### 代码 ###

import java.util.Scanner;
    
    public class Main{ 
    	public static void main(String args[]) { 
    		Scanner sc = new Scanner(System.in);
    		int flag = sc.nextInt();
    			while(sc.hasNext()) { 
    				while(sc.hasNext()) { 
    					int a = sc.nextInt();
    					int b = sc.nextInt();
    					int n = b-a;
    					int m = a;
    				System.out.println(n+" "+m);
    			    }
    			}
    		}
    }

# D、整数奇偶排序 #

**题目描述**

*  输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求:
 *  1.先输出其中的奇数,并按从大到小排列；
 *  2.然后输出其中的偶数,并按从小到大排列。

**输入**

*  任意排序的10个整数（0～100），彼此以空格分隔。

**输出**

*  可能有多组测试数据，对于每组数据，按照要求排序后输出，由空格分隔。

**样例输入 Copy**

0 56 19 81 59 48 35 90 83 75 
    17 86 71 51 30 1 9 36 14 16

**样例输出 Copy**

83 81 75 59 35 19 0 48 56 90
    71 51 17 9 1 14 16 30 36 86

**提示**

*  多组数据，注意输出格式
 *  测试数据可能有很多组，请使用while(cin>>a\[0\]>>a\[1\]>>…>>a\[9\])类似的做法来实现;
 *  输入数据随机，有可能相等。

## 我的自白 ##

*  【这个题目，我本来想的是，就是三个数组嘛，先定义一个数组用来存放输入的数据，有奇数也有偶数，然后，在判断是否整数数组里的数据是否能被2整除，如果可以，那说明就是偶数，然后放进偶数数组里，那么不能被2整除的数据就放进奇数数组里，然后都用冒泡排序排好，再放回整数数组里，然而，想的挺美的，运行结果老是说我超限了，我也改不出来，完全不知道为什么，哭唧唧QAQ~，然后，不懈努力下，我找到了大佬们的代码，通过了！】
    
    链接：[整数奇偶排序，记得点击这里哦！][Link 3]

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    			while(sc.hasNext()){ 
    				int qishu[] = new int[10];
    		        int oushu[] = new int[10];
    		        int zhengshu[] = new int[10];
    		        
    		        for(int i=0;i<10;i++)
    		            zhengshu[i]=sc.nextInt();
    		        
    		        int qi = 0,i,j;
    		        int ou = 0;
    		        for(i=0;i<10;i++) 
    		            if(zhengshu[i]%2==0)
    		            	oushu[ou++]=zhengshu[i];
    		            else 
    		            	qishu[qi++]=zhengshu[i];
    		 
    				for(i=0;i<ou;i++)
    					for(j=0;j<ou-i-1;j++)
    						if(oushu[j]>oushu[j+1])
    						{ 
    							int temp=oushu[j];
    							oushu[j]=oushu[j+1];
    							oushu[j+1]=temp;
    						}
    				
    				for(i=0;i<qi;i++)
    					for(j=0;j<qi-i-1;j++)
    						if(qishu[j]<qishu[j+1])
    						{ 
    							int temp=qishu[j];
    							qishu[j]=qishu[j+1];
    							qishu[j+1]=temp;
    						}
    				
    		        for(i=0;i<qi;i++)
    		            zhengshu[i]=qishu[i];
    		        for(j=0;j<ou;j++,i++)
    		            zhengshu[i]=oushu[j];
    		 
    		        
    		        for(i=0;i<10;i++)
    		            System.out.print(zhengshu[i]+" ");
    		   }
    	}
    
    }

# E、快速排序 #

**题目描述**

*  编程实现快速排序算法，深入理解快速排序算法的基本思想。

**输入**

*  多组输入，每组第一个数字为数组长度，然后输入一个一维整型数组。

**输出**

*  输出快速排序之后的一维整型数组（升序）

**样例输入 Copy**

6 1 8 6 5 3 4
    5 12 42 2 5 8

**样例输出 Copy**

1 3 4 5 6 8
    2 5 8 12 42

## 我的自白 ##

*  【我觉得自己能力还是不行，老师虽然上课讲过了，但到了自己写，还是错误百出，不是数组超限，就是哪里哪里有问题，所以还是需要借鉴别人写的代码，但还是像记录一下呢！这个我属实不记得在哪里找到的，看了太多代码了，也改了很多次，所以原作，抱歉哈，找不到你了】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void jiaohuan(int cbb[],int i,int j){ //比較大小，小的在前，大的在后
    		int temp = cbb[i];
    		cbb[i] = cbb[j];
    		cbb[j] = temp;
    	}
    	public static int fenqu(int cbb[],int left,int right){ //分區，前面都是小於基準的，後面都是大於基準的
    		int jizhun = cbb[left];//基準
    		
            while (left < right) { // 最终使得枢纽之前（后）的记录均不大（小）于它
            	
                while (left < right && cbb[right] >= jizhun)
                    right--;
                
                jiaohuan(cbb, left, right);// 将比枢轴记录小的记录交换到低端
     
                while (left < right && cbb[left] <= jizhun)
                    left++;
               
                jiaohuan(cbb, left, right); // 将比枢轴大的记录交换到高端
            }
            return left;
    	}
    	private static  void kuaipai(int cbb[],int left,int right){ 
    		
    		if(left<right){ 
    			
    			int r = fenqu(cbb,left,right);//p,q兩個端點，分區縮小範圍
    			kuaipai(cbb,left,r-1);
    			kuaipai(cbb,r+1,right);
    		}
    	}
    	
    	public static void kuaipai(int cbb[]){ 
    		kuaipai(cbb, 0, cbb.length - 1);
    		 
            
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int cbb[] = new int[n];
    			for(int i=0;i<cbb.length;i++)
    				cbb[i] = sc.nextInt();
    			 
    	        new Main().kuaipai(cbb);
    	        for(int i=0;i<cbb.length;i++)
    	            System.out.print(cbb[i]+" ");
    
    			
    		}
    	}
    
    }

# F、随机化快速排序 #

## 我的自白 ##

*  【老实说，这就是快速排序的优化，但是呢，嗯，不出我所料，果然但靠自己还是错误一大堆，但是，基本的代码都没变，就是在原来的代码基础上增加了两个代码，然后就OK了，链接：[快速排序][Link 4] 可以看下这个文章，我找到的不一定是为好的，就是一个小小的参考而已】

### 代码 ###

import java.util.Random;
    import java.util.Scanner;
    
    public class Main { 
    	
    	public static void jiaohuan(int cbb[],int i,int j){ //比較大小，小的在前，大的在后
    		int temp = cbb[i];
    		cbb[i] = cbb[j];
    		cbb[j] = temp;
    	}
    	public static int fenqu(int cbb[],int left,int right){ //分區，前面都是小於基準的，後面都是大於基準的
    		int jizhun = cbb[left];//基準
    		
            while (left < right) { // 最终使得枢纽之前（后）的记录均不大（小）于它
            	
                while (left < right && cbb[right] >= jizhun)
                    right--;
                
                jiaohuan(cbb, left, right);// 将比枢轴记录小的记录交换到低端
     
                while (left < right && cbb[left] <= jizhun)
                    left++;
               
                jiaohuan(cbb, left, right); // 将比枢轴大的记录交换到高端
            }
            return left;
    	}
    	private static  void kuaipai(int cbb[],int left,int right){ 
    		
    		if(left<right){ 
    			
    			int r = fenqu(cbb,left,right);//p,q兩個端點，分區縮小範圍
    			kuaipai(cbb,left,r-1);
    			kuaipai(cbb,r+1,right);
    		}
    	}
    	
    	public static void kuaipai(int cbb[]){ 
    		kuaipai(cbb, 0, cbb.length - 1);      
    	}
    	
    	public static int random(int a,int b) { 
    		Random rand=new Random();
    		int s=rand.nextInt(b);
    		return s;
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
    		
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int cbb[] = new int[n];
    			for(int i=0;i<cbb.length;i++)
    				cbb[i] = sc.nextInt();
    			
    		    int k=random(0,n);//随机选中的下标
    		    
    		    int t=cbb[k];
    		    cbb[k]=cbb[0];
    		    cbb[0]=t;//把此下标的数与0下标的数交换，作为主元，其他不用动
    		    
    		    kuaipai(cbb,0,n-1);
    		    for(int i=0;i<n;i++) { 
    		    	System.out.print(cbb[i]+" ");
    		    }
    		}
    		
    
    	}
    
    }

*  【我不是很喜欢远方，可我依旧向往】

[Link 1]: https://blog.csdn.net/qq_45823118/article/details/115282557
[Link 2]: https://blog.csdn.net/qq_44512567/article/details/113824807
[Link 3]: https://blog.csdn.net/qq_43461438/article/details/113914138?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161771528916780264036110%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161771528916780264036110&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-113914138.pc_search_result_no_baidu_js&utm_term=%E6%95%B4%E6%95%B0%E5%A5%87%E5%81%B6%E6%8E%92%E5%BA%8F
[Link 4]: https://blog.csdn.net/u014507784/article/details/71190825