欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

13种排序算法详解

程序员文章站 2022-05-23 19:45:53
第一节:随机数 1.1 Math.random()函数 Math.random随机生成0~1间的随机点数,前包括(0.00)后不包括(1) 一般没有实际意义,需要转为整数。 例程:生成30-50随机数 int t = Math.random*20+30; 1.2 Random类: 语法:Random ......

 

第一节:随机数

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

13种排序算法详解
 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

 13种排序算法详解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
13种排序算法详解
 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

13种排序算法详解
 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

13种排序算法详解
  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 }
view code