Java中的经典算法之选择排序(SelectionSort)
Java中的经典算法之选择排序(SelectionSort)
a) 原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。也就是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。(这里只介绍常用的简单选择排序)
b) 简单选择排序的基本思想:给定数组:int[] arr={里面n个数据};第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换;第2趟,在待排序数据arr[2]~arr[n]中选出最小的数据,将它与r[2]交换;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数据,将它与r[i]交换,直到全部排序完成。
c) 举例:数组 int[] arr={5,2,8,4,9,1};
-------------------------------------------------------
第一趟排序: 原始数据:5 2 8 4 9 1
最小数据1,把1放在首位,也就是1和5互换位置,
排序结果:1 2 8 4 9 5
-------------------------------------------------------
第二趟排序:
第1以外的数据{2 8 4 9 5}进行比较,2最小,
排序结果:1 2 8 4 9 5
-------------------------------------------------------
第三趟排序:
除1、2以外的数据{8 4 9 5}进行比较,4最小,8和4交换
排序结果:1 2 4 8 9 5
-------------------------------------------------------
第四趟排序:
除第1、2、4以外的其他数据{8 9 5}进行比较,5最小,8和5交换
排序结果:1 2 4 5 9 8
-------------------------------------------------------
第五趟排序:
除第1、2、4、5以外的其他数据{9 8}进行比较,8最小,8和9交换
排序结果:1 2 4 5 8 9
-------------------------------------------------------
注:每一趟排序获得最小数的方法:for循环进行比较,定义一个第三个变量temp,首先前两个数比较,把较小的数放在temp中,然后用temp再去跟剩下的数据比较,如果出现比temp小的数据,就用它代替temp中原有的数据。具体参照后面的代码示例,相信你在学排序之前已经学过for循环语句了,这样的话,这里理解起来就特别容易了。
代码示例:
//选择排序
public class SelectionSort {
public static void main(String[] args) {
int[] arr={,,,,,,};
System.out.println("交换之前:");
for(int num:arr){
System.out.print(num+" ");
}
//选择排序的优化
for(int i = ; i < arr.length - ; i++) {// 做第i趟排序
int k = i;
for(int j = k + ; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交换后:");
for(int num:arr){
System.out.print(num+" ");
}
} }
运行结果截图:
选择排序的时间复杂度:简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0。当序列反序时,移动次数最多,为3N (N - 1) / 2。
所以,综上,简单排序的时间复杂度为 O(N2)。
最新文章
- PHP基础知识第一趴
- github如何删除一个(repository)仓库
- SQL的ROW_NUMBER函数
- 安装并配置前端自动化工具——grunt
- C#开发Android环境搭建
- Java实现智能机器自动操作电脑
- How to solve ";The specified service has been marked for deletion"; error
- 数据结构(线段树):NOI 2016 区间
- HDU_1239——再次调用外星智慧
- MC-设置 止盈
- Ruby01: Beginner
- HDU-1242-Rescu
- 高校学生征信系统Postmortem结果
- 大白话5分钟带你走进人工智能-第十四节过拟合解决手段L1和L2正则
- QSetting的值不能保存。
- Java元注解—— @Retention @Target @Document @Inherited
- rtp rtcp rtsp sip协议了解方法
- 基于jquery判断浏览器版本过低代码
- REST式的web服务
- shell中date命令对month进行加减操作的bug
热门文章
- 语义化HTML:ul、ol和dl
- linux专题一之文件归档和压缩(tar、file、zip)
- 在Gridview如何进行每行单元格比较
- jQuery漂亮图标的垂直导航菜单
- ab网站压力测试
- 速战速决 (3) - PHP: 函数基础, 函数参数, 函数返回值, 可变函数, 匿名函数, 闭包函数, 回调函数
- 【Java每日一题】20161026
- Using Stored Programs with MySQLdb
- java servlet手机app访问接口(二)短信验证
- 项目总结笔记系列 Maven Session1