选择排序
文章插图
选择排序（Selection sort）是一种简单直观的排序算法 。它的工作原理如下 。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾 。以此类推，直到所有元素均排序完毕 。
选择排序的主要优点与数据移动有关 。
如果某个元素位于正确的最终位置上，则它不会被移动 。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 (n-1) 次交换 。
在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种 。
文章插图
原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见 。
JAVA 实现
package com.github.houbb.sort.core.api;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.List;/** * 选择排序 * @author binbin.hou * @since 0.0.3 */public class SelectSort extends AbstractSort { private static final Log log = LogFactory.getLog(SelectSort.class); @Override @SuppressWarnings("all") protected void doSort(List<?> original) { // 遍历，从 0，n-1 final int size = original.size(); for(int i = 0; i < size-1; i++) { int minIndex = i; // 比较，找到最小的一个 。 for(int j = i+1; j < size; j++) { if(InnerSortUtil.lt(original, j, minIndex)) { minIndex = j; } } // 进行交换 if(minIndex != i) { InnerSortUtil.swap(original, i, minIndex); } } }}可见选择排序的实现其实非常简单，也很容易理解 。直接一个循环，找到后面最小的一个元素，如果不是当前位置的元素，则进行一次交换即可 。
文章插图
比较方法为了便于复用，我们把小于的比较方法抽成工具方法，实现如下：
/** * 是否小于元素 * @param original 原始 * @param i 索引 * @param j 指定元素索引 * @since 0.0.3 */@SuppressWarnings("all")public static boolean lt(List original, int i, int j) { Comparable source = (Comparable) original.get(i); Comparable target = (Comparable) original.get(j); return source.compareTo(target) < 0;}静态化为了让这个排序使用起来更加方便，我们将其封装为静态方法：/** * 选择排序 * @param <T> 泛型 * @param list 列表 * @since 0.0.3 */public static <T extends Comparable<? super T>> void select(List<T> list) { Instances.singleton(SelectSort.class).sort(list);}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 通过API网关实现微服务管控-限流，熔断和降级
- Spring Boot 优雅地实现接口参数校验
- JavaScript数据结构——队列的实现
- 常用Java开发工具介绍
- 高可用解决方案：同城双活？异地双活？异地多活？怎么实现？
- Netflix如何实现Android与 iOS共用一套代码？
- 开源，轻松实现RTC与SIP互通
- JAVA中常见的阻塞队列详解
- Java线上CPU100% 问题排查
- JavaScript，如何在字符串中找到一个字符？
