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 }
上一篇： hdu-2544 最短路（最短路）