选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。
举个实例来看看:
- 初始: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
- i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])
- i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])
- i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])
- i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 无需交换 )
- i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])
- i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])
- i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])
- i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
- i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
- i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
由例子可以看出,选择排序随着排序的进行( i 逐渐增大),比较的次数会越来越少,但是不论数组初始是否有序,选择排序都会从 i 至数组末尾进行一次选择比较,所以给定长度的数组,选择排序的比较次数是固定的: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ,而交换的次数则跟初始数组的顺序有关,如果初始数组顺序为随机,则在最坏情况下,数组元素将会交换 n 次,最好的情况下则可能 0 次(数组本身即为有序)。
由此可以推出,选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) (选择排序只需要一个额外空间用于数组元素交换)。
实现代码:
/** * Selection Sorting */ SELECTION(new Sortable() { public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { int len = array.length; for (int i = 0; i < len; i++) { int selected = i; for (int j = i + 1; j < len; j++) { int compare = array[j].compareTo(array[selected]); if (compare != 0 && compare < 0 == ascend) { selected = j; } } exchange(array, i, selected); } } })
相关推荐
该资源提供了Java中如何实现选择排序的全面指南。文档中涵盖了选择排序的基本概念,包括如何对数组进行排序以及如何在Java中实现选择排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现选择排序,包括详细...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
详解Java常用排序算法-选择排序
Java后端算法-冒泡排序和选择排序对比
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
java排序算法-大全.rar 集合了多种java排序算法
最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构
这份资源提供了Java中如何实现快速排序的全面指南。文档中涵盖了快速排序的基本概念,包括如何对数组进行排序以及如何在Java中实现快速排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了一份全面的指南,介绍了如何在Java中实现归并排序。文档中涵盖了归并排序的基本概念,包括如何对数组进行排序以及如何在Java中...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了一份全面的指南,介绍了如何在Java中实现希尔排序。文档中涵盖了希尔排序的基本概念,包括如何对数组进行排序以及如何在Java中...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了Java中实现冒泡排序的全面指南。文档中涵盖了冒泡排序的基本概念,包括如何对数组进行排序以及如何在Java中实现冒泡排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了在Java中如何实现基数排序的全面指南。文档涵盖了基数排序的基本概念,包括如何对数组进行排序以及如何在Java中实现基数排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了在Java中如何实现计数排序的全面指南。文档涵盖了计数排序的基本概念,包括如何对数组进行排序以及如何在Java中实现计数排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
详解Java常用排序算法-基数排序
详解Java常用排序算法-桶排序
详解Java常用排序算法-计数排序
详解Java常用排序算法-堆排序
详解Java常用排序算法-希尔排序
详解Java常用排序算法-插入排序