13种排序算法详解
第一节:随机数
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 }
第二节 几种排序算法
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.将其和数组后面的每一个数进行比较,如果有比其小的交换两者位置
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 }
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 }
注:这种方法是个人在看完原理后在冒牌排序的基础上改的,较为繁琐,下面地址(参考一)的博客有更简单的方法。
参考:
(一)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 41 //2、删除学生 42 if (type ==2) { 43 44 boolean flag = false; 45 system.out.println("请输入需要删除学生的姓名"); 46 string name = sc.next(); 47 48 for(int i=0; i<students.length; i++) { 49 50 if(students[i].equals(name)) { 51 52 students[i] = students[students.length-1]; //最够一个数放在要删除的名字位置 53 students = arrays.copyof(students,students.length-1); //缩减数组 54 system.out.println("删除学生成功1"); 55 flag = true; 56 57 } 58 } 59 60 if(!flag) { 61 62 system.out.println("查无此人!"); 63 } 64 65 } 66 67 //3、修改学生 68 if (type ==3) { 69 /** 70 * equals 只是比较两个字符串字符是否相同,而不是比较两个字符串的地址值。 71 * 72 * */ 73 boolean flag = false; 74 system.out.println("请输入修改学生姓名"); 75 string name = sc.next(); 76 77 78 for (int i=0; i<students.length; i++) { 79 80 if(students[i].equals(name) ) { 81 82 system.out.println("请输入修改后学生姓名"); 83 string resetname = sc.next(); 84 flag = true; 85 students[i] = resetname; 86 system.out.println(" 修改成功!"); 87 88 } 89 } 90 91 if (!flag) { 92 system.out.println("查无此人!"); 93 } 94 95 } 96 97 //4、学生列表 98 if (type ==4) { 99 system.out.println(arrays.tostring(students)); 100 101 } 102 103 //5、查询学生 104 if (type ==5) { 105 system.out.println("请输入你要查询学生的名字"); 106 string name = sc.next(); 107 boolean flag = false; 108 for(int i=0; i<students.length; i++) { 109 if(students[i].equals(name)) { 110 111 system.out.println(students[i]); 112 113 } 114 115 } 116 117 if(!flag) { 118 119 system.out.println("查无此人!"); 120 } 121 122 } 123 124 //6、退出 125 if (type ==6) { 126 system.out.println("欢迎再次使用学生管理系统!"); 127 break; 128 } 129 130 }//while 131 } 132 133 }