首页 > > 程序设计 > Java技术 >

JavaSE学习（六）：随机数—简单的排序算法

2018-08-21 05:32:20来源：博客园阅读 ()

第一节：随机数

1.1 Math.random()函数

　　Math.random随机生成0~1间的随机点数，前包括（0.00）后不包括（1）

一般没有实际意义,需要转为整数。

例程：生成30-50随机数

int t = Math.random*20+30;

1.2 Random类：

语法：Random r = new Random();

常用的方法:

nextInt();//随机生成int类型取值范围内的整数，对我们来说意义不大。

nextInt(参数);随机生成指定范围内的整数（常用）

例: nextInt(100);随机生成0~100之间的整数

练习:

结合数组和随机数完成双色球生成

需求: 红球 1~33(包含) 号码中随机生成6个不重复的号码添加到球的数组中去蓝球 1~16(包含)号码中随机生成1个号码，扩容到红球数组中去

分析: 球的数组 int[] bool=new int[6]

第一个球: 随机生成一个号添加到数组中去后面生成的每一个球，都需要和前面每个球进行比较，只有不重复的情况下才能添加到数组中去，如果重复，舍弃，重新生成再比较，直到6个球全部添加到数组中去时完成红球功能。蓝球通过扩容添加到bool数组中去即可;

例程：DoubleColerBall.java

 1 package random;
 2 
 3 import java.util.Arrays;
 4 import java.util.Random;
 5 
 6 public class DoubleColerball {
 7     
 8     public static void main(String[] args) {
 9         
10         Random r = new Random();
11         
12         int[] redBall =new int[6];
13         int index = 0;
14         
15         redBall[index++] = r.nextInt(33)+1;            //生成第一个数
16 
17         loop:        while(true) {
18             
19             int x = r.nextInt(33)+1;
20             
21             //判断生成的x,是否在数组中
22             for (int j=0;  j<index;  j++) {
23                 //如果x在数组里面则跳出循环到loop处重新生成x,再判断，直到x不是之前数组内的数
24                 if(redBall[j] == x) {                                 
25                      //到loop处循环
26                     continue loop;                                  
27                     
28                 }
29                 
30             }        //while
31             //将x填入数组，递加index
32             redBall[index++] = x;                             
33             
34             if (index==6) {
35             
36                 break;                
37             }
38             
39         }   //while    
40     
41         System.out.println("红球生成的数为"+Arrays.toString(redBall));
42         
43         int blue = r.nextInt(16)+1;
44         
45         System.out.println("蓝球生成的数为"+blue);
46 
47         int[] ball = Arrays.copyOf(redBall, redBall.length+1);
48         
49         ball[ball.length-1] = blue;
50         
51         System.out.println("最终生成的数为"+Arrays.toString(ball));
52         
53         System.out.println("最终生成的数排序为"+Arrays.toString( sort (ball) )  );
54 
55         
56     }
57     
58 }

View Code

第二节几种排序算法

2.1 冒泡排序算法

2.1.1原理实现

将数列从小向大排序（或从大向小），将每个位置数与下个位置数比较若比后面的数大则交换位置，一轮下来能得到一个最大数，第二轮得到第二大的数......

2.1.2实例分析

例: [6,8,5,7,4]想要的最终结果是[4,5,6,7,8]

　　　6 8 5 7 4

第一轮第一次: 6 8 5 7 4

第一轮第二次: 6 5 8 7 4

第一轮第三次: 6 5 7 8 4

第一轮第四次: 6 5 7 4 8

第二轮第一次: 5 6 7 4 8

第二轮第二次: 5 6 7 4 8

第二轮第三次: 5 6 4 7 8

第三轮第一次: 5 6 4 7 8

第三轮第二次: 5 4 6 7 8

第四轮第一次: 4 5 6 7 8

规律:轮数每增加一次，比较的次数都会减少一次

　Demo2.java

View Code

2.2 选择排序法：

2.2.1原理实现

选择排序法:

第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换;

第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换;以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

例:

初始序列:{49 27 65 97 76 12 38}

第1趟:12与49交换:12{27 65 97 76 49 38}

第2趟:27不动 :12 27{65 97 76 49 38}

第3趟:65与38交换:12 27 38{97 76 49 65}

第4趟:97与49交换:12 27 38 49{76 97 65}

第5趟:76与65交换:12 27 38 49 65{97 76}

第6趟:97与76交换:12 27 38 49 65 76 97 完成

分析:

1.设定数组中第一个数为最小

2.将其和数组后面的每一个数进行比较，如果有比其小的交换两者位置

Demo2.java

 1 package random;
 2 
 3 import java.util.Arrays;
 4 /**
 5  * 
 6  * @项目名称：JavaSEDay07m
 7  * @模块功能：选择排序的实现
 8  * @模块版本：
 9  * @JDKVersions：JDK 8.0
10  * @author：  Kanekiyi
11  */
12 public class Demo3 {
13     
14     public static void main(String [] args) {
15         int[] arr={5,9,2,807,89,88};
16         int temp=0;
17         
18         //外层循环依次假设数组中的每一个数为最小值
19         for(int i=0; i<arr.length-1;i++) {
20             int min = arr[i];
21             int minIndex = i;
22             
23             for (int j=i+1; j<arr.length;j++) {        //从i的下一个开始比较
24                 if(min>arr[j]) {
25                      min = arr[j];
26                      minIndex = j;
27                 }
28                 
29             }
30             //交换最小值
31             temp = arr[i];
32             arr[i]  = arr[minIndex];
33             arr[minIndex] = temp;
34             
35         }
36         System.out.println(Arrays.toString(arr));
37 
38     }
39 }

View Code

2.3 插入排序法：

2.3.1原理实现

插入排序类似整理扑克牌，将每一张牌插到其他已经有序的牌中适当的位置。

插入排序由N-1趟排序组成，对于P=1到N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。

简单的说，就是插入排序总共需要排序N-1趟，从index为1开始，讲该位置上的元素与之前的元素比较，放入合适的位置，这样循环下来之后，即为有序数组。

2.3.2实例分析

Demo2.java

 1     //插入排序算法
 2     public static void insertSort() {
 3         int[] arr = {3,6,8,4,2,9};
 4         int[] arr2 = new int[arr.length];
 5         arr2[0] = arr[0];
 6         int temp=0;
 7 
 8         for(int i=1; i<arr.length; i++) {      //依次取出原数组插入到新数组中比较
 9             
10             for(int j=1; j<arr.length;j++) {
11                 for(int k =0; k<j+1;k++) {
12                     
13                     if(arr[i]>arr2[k]) {            //比较插入数与原数组中的数并交换位置
14                         temp = arr2[k];
15                         arr2[k] = arr[i];
16                         arr[i] = temp;
17                     }        
18                 }        
19             }        
20             //arr2[i] = temp;
21         }
22         System.out.println(Arrays.toString(arr2));
23     }

View Code

　　注：这种方法是个人在看完原理后在冒牌排序的基础上改的，较为繁琐，下面地址（参考一）的博客有更简单的方法。

　　参考：

　　（一）8种排序算法详解：https://www.cnblogs.com/0201zcr/p/4764427.html

　　（二）13种排序算法详解：http://www.cnblogs.com/whf-Staring/p/4801418.html

　　综合练习：利用数组和数据结构，完成学生管理系统（SMS1.0)的开发：

　　要求：1、创建学生数组，用于保存数据

　　　　　2、通过键盘输入数字选择功能，不同数字完成不同功能，要求对学生数字完成增删该查功能；

代码：SMS.java

  1 package random;
  2 
  3 import java.util.Arrays;
  4 import java.util.Scanner;
  5 
  6 /**
  7  * 学生管理系统1.0版本
  8  * @author  Kanekiyi
  9  * 分析：1、while 循环
 10  *            2、Scannre
 11  *               3、if 分支
 12  *               4、数组 扩容 缩容 遍历
 13  *      String
 14  * */
 15 
 16 public class SMS {
 17     
 18     public static void main(String[] args) {
 19         System.out.println("欢迎使用学生管理系统1.0版本");
 20         
 21         String[] students = {"刘一","孙二","张三","李四"};
 22         
 23         Scanner sc = new Scanner(System.in);
 24         
 25         while(true) {
 26             System.out.println("1.添加学生 2.删除学生 3.修改学生 4.学生列表 5.查询学生 6.退出");
 27             System.out.println("请输入数字选择功能");
 28 
 29             int type = sc.nextInt();
 30             
 31             //1添加学生
 32             if (type ==1) {
 33                 System.out.println("请输入添加学生姓名");
 34                 String name = sc.next();
 35                 students = Arrays.copyOf(students,students.length+1);
 36                 students[students.length-1] = name;
 37                 System.out.println("添加成功");
 38             }
 39         
 40             //2、删除学生
 41             if (type ==2) {
 42                 boolean flag = false;
 43                 System.out.println("请输入需要删除学生的姓名");
 44                 String name = sc.next();
 45 
 46                 for(int i=0; i<students.length; i++) {
 47                     if(students[i].equals(name)) {
 48                         //最后一个数放在要删除的名字位置
 49                         students[i] = students[students.length-1];       
 50                         //缩减数组
 51                         students = Arrays.copyOf(students,students.length-1);                 
 52                         System.out.println("删除学生成功1");
 53                         flag = true;
 54                     }
 55                 }
 56                 
 57                 if(!flag) {
 58                     System.out.println("查无此人！");
 59                 }
 60                 
 61             }    
 62             
 63             //3、修改学生
 64             if (type ==3) {
 65                 /**
 66                  * equals 只是比较两个字符串字符是否相同，而不是比较两个字符串的地址值。
 67                  * 
 68                  * */
 69                 boolean flag = false;
 70                 System.out.println("请输入修改学生姓名");
 71                 String name = sc.next();
 72 
 73                 for (int i=0; i<students.length; i++) {
 74                     if(students[i].equals(name) ) {
 75                         System.out.println("请输入修改后学生姓名");
 76                         String resetName = sc.next();
 77                         flag = true;
 78                         students[i] = resetName;
 79                         System.out.println(" 修改成功！");
 80                     }
 81                     
 82                 }
 83                 
 84                 if (!flag) {
 85                     System.out.println("查无此人！");
 86                 }
 87                                 
 88             }
 89             
 90             //4、学生列表
 91             if (type ==4) {
 92                     System.out.println(Arrays.toString(students));
 93             }            
 94             
 95             //5、查询学生
 96             if (type ==5) {
 97                 System.out.println("请输入你要查询学生的名字");
 98                 String name = sc.next();
 99                 boolean flag = false;
100                 for(int i=0; i<students.length; i++) {
101                     if(students[i].equals(name)) {
102                         System.out.println(students[i]);
103                     }
104                     
105                 }
106                 
107                 if(!flag) {
108                     System.out.println("查无此人！");
109                 }
110                 
111             }
112             
113             //6、退出
114             if (type ==6) {
115                 System.out.println("欢迎再次使用学生管理系统！"); 
116                 break;
117             }
118     
119         }//while
120         
121     }
122 
123 }