我的Java开发学习之旅------>Java经典排序算法之选择排序

简介: 一、算法原理 对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置, 接着第二次比较,前面“后一个元素”现变成了“前一个元素”,继续跟他的“后一个元素”进行比较如果后面的元素比 他要小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了, 然后进行判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值,这样就找到整 个数组中最小的数了。


一、算法原理

对比数组中前一个元素跟后一个元素的大小,如果后面的元素比前面的元素小则用一个变量k来记住他的位置,
接着第二次比较,前面“后一个元素”现变成了“前一个元素”,继续跟他的“后一个元素”进行比较如果后面的元素比
他要 小则用变量k记住它在数组中的位置(下标),等到循环结束的时候,我们应该找到了最小的那个数的下标了,
然后进行 判断,如果这个元素的下标不是第一个元素的下标,就让第一个元素跟他交换一下值, 这样就找到整
个数组中最小的 数了。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。


二、算法分析

1.时间复杂度
选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。
比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
2.稳定性
选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法。

三 、算法演示



四、代码实现

public class SelectSort {
	public static void selectSort(int[] a) {
		int minIndex = 0;
		int temp = 0;
		if ((a == null) || (a.length == 0))
			return;
		for (int i = 0; i < a.length - 1; i++) {
			minIndex = i;// 无序区的最小数据数组下标
			for (int j = i + 1; j < a.length; j++) {
				// 在无序区中找到最小数据并保存其数组下标
				if (a[j] < a[minIndex]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				// 如果不是无序区的最小值位置不是默认的第一个数据,则交换之。
				temp = a[i];
				a[i] = a[minIndex];
				a[minIndex] = temp;
			}
			System.out.println("第" + (i + 1) + "趟:");
			printArray(a);
		}
	}

	private static void printArray(int[] source) {
		for (int i = 0; i < source.length; i++) {
			System.out.print("\t" + source[i]);
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] source = { 70,30,40,10,80,20,90,100,75,60,45};
		System.out.println("初始关键字:");
		printArray(source);

		selectSort(source);

		System.out.println("\n\n排序后:");
		printArray(source);
	}
}




五、运行结果

初始关键字:
	70	30	40	10	80	20	90	100	75	60	45
第1趟:
	10	30	40	70	80	20	90	100	75	60	45
第2趟:
	10	20	40	70	80	30	90	100	75	60	45
第3趟:
	10	20	30	70	80	40	90	100	75	60	45
第4趟:
	10	20	30	40	80	70	90	100	75	60	45
第5趟:
	10	20	30	40	45	70	90	100	75	60	80
第6趟:
	10	20	30	40	45	60	90	100	75	70	80
第7趟:
	10	20	30	40	45	60	70	100	75	90	80
第8趟:
	10	20	30	40	45	60	70	75	100	90	80
第9趟:
	10	20	30	40	45	60	70	75	80	90	100
第10趟:
	10	20	30	40	45	60	70	75	80	90	100


排序后:
	10	20	30	40	45	60	70	75	80	90	100





==================================================================================================

  作者:欧阳鹏  欢迎转载,与人分享是进步的源泉!

  转载请保留原文地址http://blog.csdn.net/ouyang_peng

==================================================================================================





相关文章
|
6天前
|
算法 Java
Java基础学习day03-作业
本内容包含多个Java编程案例,涵盖条件判断、循环、数组、随机数生成、素数判断等基础算法练习,适用于巩固Java语法与逻辑思维训练。
54 6
|
3天前
|
Java
Java基础学习day05-作业
本文为Java基础学习第五天作业,通过五个案例练习类与对象的定义、构造方法、set/get方法及成员方法的应用。涵盖女友、学生、教师、手机和电影等类的设计与测试,强化面向对象编程基础。
22 2
|
3天前
|
安全 Java 编译器
Java基础学习day06
本节学习Java继承与多态核心概念:继承通过extends实现,子类可复用父类非私有成员,支持单继承与多层继承,遵循就近原则并可用super调用父类成员;方法重写需满足权限与返回值约束,常用于重写toString等。多态基于继承,实现父类引用指向子类对象,提升扩展性但无法直接访问子类独有方法,可通过instanceof安全类型转换。
47 2
|
6天前
|
存储 Java 索引
Java基础学习day04
本节讲解Java数组基础,包括静态与动态初始化、元素访问及遍历方法,并介绍二维数组的定义与使用,帮助理解程序数据存储方式。
31 5
|
6天前
|
Java
Java基础学习day02-作业
本内容包含13个Java编程练习需求,涵盖变量定义、数据类型转换、运算符使用、键盘输入及条件判断等基础语法实践,适合初学者巩固Java核心基础知识。
24 5
|
4天前
|
存储 Java
Java基础学习day05
本节介绍Java面向对象编程基础,涵盖类与对象的概念、构造器、this关键字、封装、Javabean及static修饰符的使用。重点讲解如何通过类设计对象、实现数据封装与方法暴露,并理解静态成员的特点与应用场景。
28 2
|
4天前
|
Java
Java基础学习day04-作业
本作业包含8个Java编程案例,涵盖数组的定义与遍历、求和、最值计算、去极值求平均、元素倍增、二维数组行和计算及查找指定元素等内容,旨在巩固Java基础语法与数组操作技能。
44 1
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
238 0
|
存储 算法 Java
数据结构算法学习打卡week2 (Java)
数据结构算法学习打卡week2 (Java)
173 0
|
Rust 算法 安全
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)

热门文章

最新文章