李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--选择排序
Leefs
2020-02-01 PM
1677℃
0条
# 数据结构和算法学习--选择排序 ### 一、基本介绍 选择排序属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。 ### 二、选择排序的思想 选择排序(select sorting)也是一种简单的排序方法。它的**基本思想**是:第一次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1]~arr[n-1]中选取最小值,与arr[1]交换,第三次从arr[2]~arr[n-1]中选取最小值,与arr[2]交换,…,第i次从arr[i-1]~arr[n-1]中选取最小值,与arr[i-1]交换,…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。 ### 三、选择排序思路分析图 ![15.选择排序算法01.png][1] **对一个数组的选择排序进行演示** ``` 原始的数组 : 101, 34, 119, 1 第一轮排序 : 1, 34, 119, 101 第二轮排序 : 1, 34, 119, 101 第三轮排序 : 1, 34, 101, 119 ``` **说明:** 1.选择排序一共有`数组大小-1`轮排序 2.每1轮排序,又是一个循环,循环的规则: 2.1 先假定当前这个数是最小数 2.2 然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标 2.3 当遍历到数组的最后时,就得到本轮的最小数和下标 2.4 进行交换 ### 三、**选择排序应用实例**: **有一群牛** **,** **颜值分别是** 101, 34, 119, 1 **请使用选择排序**从低到高**进行排序** **[**101, 34, 119, 1**]** **选择排序代码实现** ```java public class SelectSort { public static void main(String[] args) { int[] arr = {1,34,109,110}; selectSort(arr); } public static void selectSort(int[] arr){ for(int i=0;i
arr[j]){//说明假定的最小值并不是最小值 min = arr[j]; minIndex = j; } } //将最小值,放在arr[0],进行交换 if(minIndex!=i){ arr[minIndex]=arr[i]; arr[i]=min; } } System.out.println(Arrays.toString(arr)); } } ``` > 运行结果 ``` [1, 34, 109, 110] ``` 完整代码【含80000个随机数进行性能测试】 ```java //选择排序 public class SelectSort2 { public static void main(String[] args) { //int [] arr = {101, 34, 119, 1, -1, 90, 123}; //创建要给80000个的随机的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 } System.out.println("排序前"); //System.out.println(Arrays.toString(arr)); Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); selectSort(arr); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序前的时间是=" + date2Str); //System.out.println("排序后"); //System.out.println(Arrays.toString(arr)); } //选择排序 public static void selectSort(int[] arr) { //在推导的过程,我们发现了规律,因此,可以使用for来解决 //选择排序时间复杂度是 O(n^2) for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值,并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值,放在arr[0], 即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } //System.out.println("第"+(i+1)+"轮后~~"); //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101 } /* //使用逐步推导的方式来,讲解选择排序 //第1轮 //原始的数组 : 101, 34, 119, 1 //第一轮排序 : 1, 34, 119, 101 //算法 先简单--》 做复杂, 就是可以把一个复杂的算法,拆分成简单的问题-》逐步解决 //第1轮 int minIndex = 0; int min = arr[0]; for(int j = 0 + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的最小值,并不是最小 min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值,放在arr[0], 即交换 if(minIndex != 0) { arr[minIndex] = arr[0]; arr[0] = min; } System.out.println("第1轮后~~"); System.out.println(Arrays.toString(arr));// 1, 34, 119, 101 //第2轮 minIndex = 1; min = arr[1]; for (int j = 1 + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值,并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值,放在arr[0], 即交换 if(minIndex != 1) { arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第2轮后~~"); System.out.println(Arrays.toString(arr));// 1, 34, 119, 101 //第3轮 minIndex = 2; min = arr[2]; for (int j = 2 + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值,并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值,放在arr[0], 即交换 if (minIndex != 2) { arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第3轮后~~"); System.out.println(Arrays.toString(arr));// 1, 34, 101, 119 */ } } ``` 运行结果 ``` 排序前 排序前的时间是=2020-02-01 21:01:32 排序前的时间是=2020-02-01 21:01:34 ``` [1]: https://lilinchao.com/usr/uploads/2020/02/2136545149.png
标签:
数据结构和算法
,
排序
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/532.html
上一篇
数据结构和算法学习--冒泡排序
下一篇
数据结构和算法学习--插入排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
ClickHouse
链表
Shiro
栈
高并发
工具
稀疏数组
Golang
DataWarehouse
Thymeleaf
数据结构和算法
nginx
MyBatis
Eclipse
Jquery
gorm
Java编程思想
JavaScript
Flink
Typora
ajax
Zookeeper
二叉树
并发线程
排序
Netty
容器深入研究
锁
SpringBoot
Tomcat
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞