Java常见经典算法详解-选择排序(Selection Sort)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java常见经典算法详解-选择排序(Selection Sort)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1817字，纯文字阅读大概需要3分钟。

内容图文

选择排序(Selection Sort)算法简介：

  选择排序是利用逐个选择的方式进行排序，逐个选择出数组中的最小（或最大）的元素，顺序放在已排好序的序列后面，直到全部记录排序完毕。

选择排序(Selection Sort)算法原理：

例如我们有一个数组，我们需要把较小的元素排在前面，把较大的元素排在后面，那么需要选择出最小元素并将其排在序列最前：

• 从待排序列中选出最小（或最大）的一个元素，记录其下标的位置；
• 将记录的下标值与待排序列的第一个元素进行交换；
• 以此类推，直到全部待排序列的元素排完。

举例说明：

现在需要对数组序列 6 1 7 8 9 3 5 4 2 运用选择排序算法从小到大排序。

第一轮：最小元素为1，把1放在首位，也就是1和6互换位置：1 6 7 8 9 3 5 4 2 

第二轮：将排序好的元素以外的序列6 7 8 9 3 5 4 2进行比较，最小元素为2，将2与第二位的6互换位置：1 2 7 8 9 3 5 4 6 

第三轮：将排序好的元素以外的序列7 8 9 3 5 4 6 进行比较，最小元素为3，将3与第三位的7互换位置：1 2 3 8 9 7 5 4 6 

.................

第n轮：重复同样的操作直到所有数字都归位为止，排序完成。

选择排序(Selection Sort)代码实现：

public class Demo {
 
	public static void main(String[] args) {
		int[] array= {6,1,7,8,9,3,5,4,2};
		int[] newarray=selectionSort(array);
		for(int arr:newarray) {
			System.out.print(arr+" ");
		}
	}
	public static int[] selectionSort(int[] array){
		//外层循环,控制选择的次数
		for(int i=0;i<array.length-1;i++) {
			int min_index=i;
			//内存循环
			for(int j=i+1;j<array.length;j++) {
				if(array[j]<array[min_index]) {
					min_index=j;
				}
			}
			if(min_index!=i) {
				int temp=array[i];
				array[i]=array[min_index];
				array[min_index]=temp;
			}
		}
		return array;
	}
}

选择排序(Selection Sort)的时间复杂度：

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数.....到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是(n-1)+(n-2) +...+1≈n²/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O(n²)。

内容总结

以上是互联网集市为您收集整理的Java常见经典算法详解-选择排序(Selection Sort)全部内容，希望文章能够帮你解决Java常见经典算法详解-选择排序(Selection Sort)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---